[Algorithm] 숫자 암호 만들기 (password)

0. 문제

link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-number-pass/description

코드트리

주어진 숫자를 쪼개어 암호를 만들려고 한다. 암호를 만드는 과정은 다음과 같다.

1. 숫자를 1, 2, 3, 4의 합으로 바꾼다.

2. 숫자의 합에서 사용된 숫자를 일렬로 나열한다.

 

일례로, 3을 활용하면

1+1+1 = 111

2+1 = 21

1+2 =12

3 = 3

 

4개의 암호를 만들 수 있다. 숫자 n이 주어졌을 때 만들 수 있는 암호의 가짓수를 구해보자.

 

1. 풀이 

 

이는 동적 계획법으로 해결할 수 있다. dp[i]를 i로 만들 수 있는 암호의 가짓수라고 하면, dp[i-1], ..., dp[i-4] 의 뒤에 1, 2, 3, 4를 각각 붙이기만 하면 되기 때문이다. 순서를 고려하는 것 때문에 헷갈릴 수 있는데, 어차피 그 순서는 dp[i-k]에서 다 고려해놨다.

따라서 dp[i] += dp[i-k] (for k in range(4)) 가 되겠다. 

 

초기화가 중요한 문제인데, 나머지는 아직 구하지 않았으니 0으로 설정해도, dp[0]을 어떻게 설정하느냐가 관건이다.

아무것도 사용하지 않아 빈 문자열이 나온 경우를 1로 간주해주는 것이 중요하다. 그래야 dp[1] = dp[1] + dp[0] 이 되어서 dp[1] = 1이라는 값을 도출할 수 있다.

 

2. 구현

 

n = int(input())
dp = [0 for i in range(n+1)]
nums = [1, 2, 3, 4]
dp[0] = 1

# 4는 단독으로 표현되지 않기 때문에 base를 4까지 넣어줘야 한다.

for i in range(5, n+1):
    for num in nums:
        if i - num >= 0:
            dp[i] += dp[i - num]

print(dp)