개발하지연

문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 기록 (dp 4일차) 저번에 풀었던 타일링 문제와 비슷했다. 달라진 점은 2x2타일이 추가되었다는 점. >> 2021.07.23 - [알고리즘] - [백준 11726번] 2xn 타일링 (python) 문제는 각 2xn을 타일로 채우는 방법 수를 dp배열에 저장하여, dp[n]=dp[n-1](세로블럭 추가)+dp[n-2]*2(가로블럭2개 추가 or 2x2블럭 추가)의 점화식을 세워 계산하면 된다. 코드 n = int(input()) dp = [0, 1, 3] for i in range(3, n+1): dp.append(dp[i-1]+dp[i-2]*2..

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 ..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 기록 (dp 3일차) 계산을 잘못해서 한참 틀리다가 겨우 맞았다. 아래 결과들이 지저분해서 맞은 결과만 기록해야겠다..ㅎ 세로블럭 1개를 제외한 경우의 수와 가로블럭 2개를 제외한 경우의 수x2(세로2개/가로2개)를 더해서 계산했다가 나중에 세로블럭 1개를 제외한 경우의 수와 세로블럭 2개를 제외한 경우의 수가 겹친다는 사실을 알게되서 수정했다. 혹시 도움이 될까 해서 n 10까지의 결과를 적어놓는다. [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] 이 문제는 2xn의 직사각형을 채우는 방법의 수를 저장한 배열 d..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 기록 (dp 3일차) 여러 개의 테스트케이스가 입력으로 들어오기 때문에 기존에 n까지의 배열을 만들었던 방법과 다르게 풀어야해서 당황했었다. 가장 큰 테스트케이스로 배열을 만들어야하나, Top-down방식으로 배열을 만들어나가야 하나하다가 n이 12로 제한되어있는 조건을 보고 처음에 배열을 만들어 놓기로 했다. 이 문제는 n을 1,2,3의 합으로 나타내는 방법 수를 저장하는 배열 dp를 만들어, dp[n] = ..