[백준/Python] 12101번: 1, 2, 3 더하기 2

문제

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

12101번: 1, 2, 3 더하기 2

---

문제 요약

정수 n을 입력 받고, n을 1, 2, 3의 합으로 나타내는 방법을 사전 순으로 정렬하고, k번째 식을 출력한다.

(1 ≤ n ≤ 10)

 

ex) 정수 4를 1, 2, 3의 합으로 나타내는 방법

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

 

위 방법을 사전 순으로 정렬하면,

 

1+1+1+1

1+1+2

1+2+1

1+3

2+1+1

2+2

3+1

---

코드

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

dp = [[] for _ in range(11)]
# dp[i][j]는 i를 1, 2, 3의 합으로 나타내는 j + 1번째 방법

dp[1] = [[1]]
dp[2] = [[1, 1], [2]]
dp[3] = [[1, 1, 1], [1, 2], [2, 1], [3]]

for i in range(4, n + 1):
    for j in range(len(dp[i-1])):
        dp[i].append([1] + dp[i-1][j])

    for j in range(len(dp[i-2])):
        dp[i].append([2] + dp[i-2][j])

    for j in range(len(dp[i-3])):
        dp[i].append([3] + dp[i-3][j])

if k > len(dp[n]):
    print(-1)
else:
    print('+'.join(list(map(str, dp[n][k - 1]))))

---

코드 설명

정수 i를 1, 2, 3으로 나타내는 방법을 사전 순으로 정렬한 배열

= [[1] + 정수 i - 1을 1, 2, 3으로 나타내는 방법을 사전 순으로 정렬한 배열]

+ [[2] + 정수 i - 2을 1, 2, 3으로 나타내는 방법을 사전 순으로 정렬한 배열]

+ [[3] + 정수 i - 3을 1, 2, 3으로 나타내는 방법을 사전 순으로 정렬한 배열]

 

4를 i라고 했을 때, i - 1, i - 2, i - 3은 각각 3, 2, 1이다.

 

3을 1, 2, 3으로 나타낸 방법을 사전 순으로 정렬한 배열은

[1 + 1 + 1]

[1 + 2]

[2 + 1]

[3]

이다.

 

[1] + 3을 1, 2, 3으로 나타낸 방법을 사전 순으로 정렬한 배열은

[1 + 1 + 1 + 1]

[1 + 1 + 2]

[1 + 2 + 1]

[1 + 3]

이다.

 

같은 방법으로

 

2를 1, 2, 3으로 나타낸 방법을 사전 순으로 정렬한 배열은

[1 + 1]

[2]

이다.

 

[2] + 2를 1, 2, 3으로 나타낸 방법을 사전 순으로 정렬한 배열은

[2 + 1 + 1]

[2 + 2]

이다.

 

마지막으로

 

1을 1, 2, 3으로 나타낸 방법을 사전 순으로 정렬한 배열은

[1]

이다.

 

[3] + 1를 1, 2, 3으로 나타낸 방법을 사전 순으로 정렬한 배열은

[3 + 1]

이다.

 

따라서 4

를 1, 2, 3으로 나타내는 방법을 사전 순으로 정렬한 배열 (2차원 배열)은

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]] 이다.

 

코드 상으로는 메모이제이션 테이블 dp에 i를 1, 2, 3으로 나타내는 방법을 사전 순으로 정렬한 배열(2차원 배열)을 저장하고, 입력 받은 정수 n, k에 해당하는 dp[n][k-1]값을 형식에 맞게 출력한다.

 

+ dp에 미리 11개의 배열을 생성하여 n이 1, 2, 3일 때 발생하는 오류를 방지한다.

+ k가 dp[n]의 길이보다 크면 -1을 출력한다. (인덱스를 벗어나므로)