[boj] 백준 12101 1, 2, 3 더하기 2 python 풀이

문제

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

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

 

문제 풀이

dp로 푸는 경우)

https://cccaaa.tistory.com/84 처럼 dp를 구성하고, 3이하의 표현방법이 나올때까지 돌리기..

그림으로 나타내면

dp 설명

이므로, n<=3의 표현방법으로 나타낼 수 있을 때까지 쪼개면서 표현식 만들기.

 

백트래킹으로 푸는 경우)

이 문제는 사전순 정렬이 조건이기 때문에 백트래킹으로도 풀 수 있음.

range(1,4)를 하나씩 더해주면서 k번째 표현일 때 출력해주기.

 

코드

dp 코드)

import sys
input = sys.stdin.readline

rep = [[] for _ in range(11+1)]
rep[1] = ['1']
rep[2] = ['1+1','2']
rep[3] = ['1+1+1','1+2','2+1','3']

dp = [0 for _ in range(11+1)]
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,len(dp)):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

n, k = map(int,input().split())
res = ''
if k > dp[n]:
    print(-1)
    exit()
    
while True:
        
    if n<=3:
        res+=rep[n][k-1]
        break

    if k<=dp[n-1]:
        res+='1+'
        n-=1
    elif k<=(dp[n-1]+dp[n-2]):
        res+='2+'
        k-=(dp[n-1])
        n-=2
    else:
        res+='3+'
        k-=(dp[n-1]+dp[n-2])
        n-=3

print(res)

 

백트래킹 코드)

import sys
input = sys.stdin.readline

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

total = []
cnt = 0

def back():
    global cnt
    if sum(total)>n:
        return
    
    if sum(total) == n:
        if cnt != k-1:
            cnt += 1
            return
        else:
            print(*total, sep='+')
            exit()

    for i in range(1,4):
        total.append(i)
        back()
        total.pop()

back()
print(-1)