백준 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=2인 경우 예시

N=4인 경우

N=4인 경우 예시

N=2인 경우를 포함하고 있는 것을 알 수 있습니다.

그러므로 위의 경우 3*3 = 9가지 경우의 수가 있습니다.

그 다음 N=4인 경우에만 나오는 수를 구해줍니다.

N=4인 경우에만 나오는 예시

위와 같은 경우가 2개 더 나오게 됩니다.

dp[4]=3*3+2 입니다.

 

N=6인 경우까지 구하면 점화식을 구할 수 있습니다.

 

3*N크기의 경우의 수

N-2

2와 N-2로 나누었을 경우 3*2 크기일 때만 나타나는 경우는 3가지이므로 dp[N-2]*3의 경우의 수를 가지게 됩니다.

N-4

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])