백준 12101 - 1, 2, 3 더하기 2 (Python)

문제

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

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

풀이

n,k = map(int,input().split())
save = {}
save[1] = ["1"]
save[2] = ["1+1","2"]
save[3] = ["1+2","1+1+1","2+1","3"]
for i in range(4,12):
    save[i] = []
    for j in save[i-1]:
        save[i].append(j+"+1")
    for j in save[i-2]:
        save[i].append(j+"+2")
    for j in save[i-3]:
        save[i].append(j+"+3")            

if k <= len(save[n]):
    print(sorted(save[n])[k-1])
else:
    print(-1)

1, 2, 3 더하기의 2번째 시리즈이다. 

역시 9095번에서 설명한 원리를 똑같히 적용하면 된다.

해당 문제의 풀이는 아래 참고

2024.02.12 - 백준 9095 - 1, 2, 3 더하기 (Python)

백준 9095 - 1, 2, 3 더하기 (Python)

 

n이 11이하이므로 그냥 다 만들어 놓고 출력해도 메모리초과나 시간초과가 나지 않는다.

저번 글에서 설명했듯이 1, 2, 3을 이용해서 어떤 숫자 i를 만드는 경우는 아래 세가지 중 한가지이다

 

1) i-3을 만드는 각각의 경우에 +3을 하는 경우

2) i-2를 만드는 각각의 경우에 +2를 하는 경우

3) i-1를 만드는 각각의 경우에 +1 을 하는경우

 

n이 1, 2, 3 일때 해당하는 각 경우의 수를 넣어두고 이후 숫자를 만드는 경우는 n-3, n-2, n-1을 만드는 경우들에 +3, +2, +1을 각각 붙혀서 리스트에 추가해주는 식으로 구현하였다.

 

이후 k값이 리스트의 총 경우의 수를 넘어서면 -1을 출력하고

아니면 n을 만드는 경우의 수를 정렬하고 k 번째를 출력해주었다.