[백준 BOJ] 2225 합분해 (python)

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

 

🔥 작성 코드

n, k = map(int, input().split())

nl = [[0 for _ in range(n+1)] for _ in range(k+1)]
for i in range(n+1):
    nl[1][i] = 1
    if k >= 2:
        nl[2][i] = i+1
if k >= 3:
    for i in range(3, k+1):
        nl[i][0] = 1
        for j in range(1, n+1):
            nl[i][j] = nl[i-1][j] + nl[i][j-1]

print(nl[k][n]%1000000000)

 

⭕ 해설

 

1. 일단 정수 k개가 있을 때 n을 나타낼 수 있는 경우의 수를 생각해봤습니다.
2. k개 한개라면 자기 자신만 쓸 수 있으므로 n이 무엇이든 답은 1입니다.
3. k가 2라면 0+n, 1+(n-1), 2+(n-2), ..., (n-1)+1, n+0 으로 답은 n+1입니다.
4. 이렇게 따져본다면 k=2 일때는 k=1일때 구할 수 있는 수들에 0~n까지 더해준 값이 됩니다.
   • 만약 n=3이라면, k=1일 때 구할 수 있는 경우의 수 뒤에 각각 0~n까지 더해주면 k=2를 만들 수 있음.
   • n=0 : 0      +3
   • n=1 : 1      +2
   • n=2 : 2      +1
   • n=3 : 3      +0
5. 따라서 k=2에서 n=3일 때의 값은 k=1에서 n=0~3까지의 값의 합인 4가 됩니다. 
6. 표를 만들어서 n=0~6일 때 k=4까지 알아보겠습니다. 

n	k=1	k=2	k=3	k=4
0	1	1	1	1
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20
4	1	5	15	35
5	1	6	21	56
6	1	7	28	84

 만약 n =6, k=4라면 3가지 수를 더해서 만들 수 있는(k=3일 때) 0~6까지의 경우의 수를 모두 더한 값이 됩니다.

(1+3+6+10+15+21+28 = 84)

 

 그렇기 때문에, n=5, k=4일 때의 값은 5가지 수를 더해서 만들 수 있는 0~5까지의 수를 모두 더한 값이므로

n=5, k=4의 값과 n=6, k=3을 더한 값이 n=6, k=4의 값이 됩니다.

(56+28 = 84)

 

 제가 작성한 코드는 이 방식을 그대로 구현한 코드이며, 편의상 k=0일 때는 모두 0으로 만들어두고,

k=1일때의 값을 모두 1, k=2일 때의 값을 n+1로 담아둔 뒤, k=3부터 주어진 k까지 값을 저장해나갔습니다.

(만약 k가 3이나 2보다 작을 경우를 문제에서 요구하게 될 수도 있어 if문을 활용하였습니다. 사실 k=1일 때만 미리 값을 넣어줘도 됩니다.)

🚨 0은 항상 0만 더해줄 수 있으므로 n=0이라면 k값에 상관없이 답은 1이 됩니다.

 그래서 j-1에서 오류가 나지 않도록 j는 1부터 돌리고, 0의 자리는 1로 미리 채워주었습니다.