백준 2225번 합분해, 2133번 타일 채우기 (Python, DP)
2225번 합분해
0~N개의 숫자 K개를 더해서 N을 만드는 경우의 수를 구하는 문제입니다.
덧셈의 순서가 바뀐 경우 다른 경우로 셉니다.
풀이
다이나믹 프로그래밍을 이용해 이전의 결과값들을 저장해서 다음에 사용할 수 있도록 했습니다.
dp 배열의 행은 N을 나타내고 열은 K를 나타내도록 2차 배열로 선언했습니다.
1️⃣
N이 1인 경우 K에 상관 없이 dp[1][k]=k입니다.
1을 1개의 숫자로 만드는 방법은 1
1을 2개의 숫자로 만드는 방법은 0+1, 1+0
1을 3개의 숫자로 만드는 방법은 0+0+1, 0+1+0, 1+0+0
...
이므로 dp[1][i]=i 입니다.
2️⃣
k가 2인 경우 N에 상관 없이 dp[n][k] = n+1 입니다.
1을 2개의 숫자로 만드는 방법은 0+1, 1+0
2를 2개의 숫자로 만드는 방법은 0+2, 1+1, 2+0
3을 2개의 숫자로 만드는 방법은 0+3, 1+2, 2+1, 3+0
...
이므로 dp[i][j] = i+1
3️⃣
위의 수를 dp에 세팅을 해두면 이를 가지고 다음 dp 내부를 채울 수 있습니다.
아래 표를 확인해보면 점화식을 세울 수 있습니다.
| K=1 | K=2 | K=3 | K=4 | |
| N=1 | 1 | 2 | 3 | 4 |
| N=2 | 1 | 3 | 6 | 10 |
| N=3 | 1 | 4 | 10 | 20 |
| N=4 | 1 | 5 | 16 | 36 |
위의 표를 확인해보면 다음과 같은 점화식을 세울 수 있습니다.
dp[i][k]=dp[i-1][k]+dp[i][k-1]
이를 이용해 문제를 풀 수 있습니다.
전체 코드
N, K = list(map(int, input().split()))
dp = [[0 for __ in range(201)] for _ in range(201)]
for i in range(201):
dp[1][i] = i
dp[i][2] = i+1
dp[i][1] = 1
for i in range(2, 201):
for j in range(2, 201):
dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % 1_000_000_000
print(dp[N][K])
2133번 타일 채우기
3*N 벽을 1*2, 2*1 크기의 타일로 채우는 경우의 수를 구하는 문제입니다.
3*N 크기의 벽은 N이 홀수일 경우 전체 칸의 넓이가 홀수가 나오므로 타일로 모든 칸을 채울 수 있는 경우가 없습니다.
그러므로 N이 짝수인 경우만 확인하면 됩니다.
N=2인 경우
N=4인 경우
N=2인 경우를 포함하고 있는 것을 알 수 있습니다.
그러므로 위의 경우 3*3 = 9가지 경우의 수가 있습니다.
그 다음 N=4인 경우에만 나오는 수를 구해줍니다.
위와 같은 경우가 2개 더 나오게 됩니다.
dp[4]=3*3+2 입니다.
N=6인 경우까지 구하면 점화식을 구할 수 있습니다.
3*N크기의 경우의 수
2와 N-2로 나누었을 경우 3*2 크기일 때만 나타나는 경우는 3가지이므로 dp[N-2]*3의 경우의 수를 가지게 됩니다.
4와 N-2로 나누었을 경우 3*4 크기일 때만 나타나는 경우는 2가지 였습니다. 그러므로 dp[N-4]*2 입니다.
이 후, 6과 N-6, 8과 N-8로 나누는 경우에도 6*8 크기, 8*8 크기에만 나타나는 경우는 2가지 였습니다.
그러므로 6과 N-6으로 나누는 경우는 dp[N-6]*2, 8과 N-8로 나누는 경우는 dp[N-8]*2입니다.
그리고 3*N 크기에서만 나타나는 경우 또한, 2가지입니다.
그러므로 dp[N]= (2*3일 때만 나오는 경우)*dp[N-2] + (4*3일 때만 나오는 경우의 수)*dp[N-4] ... + 2
dp[N]= 3*dp[N-2] + 2 * (dp[N-4] + dp[N-6] + ... ) + 2가 됩니다.
이 점화식을 통해 풀 수 있습니다.
전체 코드
N = int(input())
dp = [0 for _ in range(31)]
dp[2] = 3
dp[4] = 11
for i in range(6, 31, 2):
if i % 2 == 1:
continue
dp[i] = dp[i-2]*3+sum(dp[:i-2])*2+2
print(dp[N])