알고리즘 - DP (백준 1463, 11726, 11727, 9095)

1463

n = int(input())
dp = [0]*(n+1)
for i in range(1, n+1):  # 0과 1은 연산이 필요가 없어 [0, 0]이다. 때문에 for문은 2부터 시작해야 한다.    
    dp[i] = dp[i-1]+1
    if i%3==0:
        dp[i] = min(dp[i], dp[i//3]+1)
    if i%2==0:
        dp[i] = min(dp[i], dp[i//2]+1)
print(dp[n])
"""
count: 0,1:0 2:1 3:1 4:2 5:3
for문이 0, 1, 2로 시작할 때의 n=5일때 차이점(n을 인덱스에 맞추고, 값에는 count를 넣는다)
0시작 : [1, 2, 3, 3, 4, 5]
1시작 : [0, 1, 2, 2, 3, 4]
2시작 : [0, 0, 1, 1, 2, 3]
"""

 

11726

num = int(input())  # 가로길이
dp = [0]*1001
dp[1]=1  # 2*1일경우 2*1블록 1개이므로 1을 넣는다 
dp[2]=2  # 2*2일경우 2*1블록 2개이므로 2를 넣는다
for i in range(3, 1001):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[num]%10007)
# 1*2블록, 2*2블록 갖고 채운다 생각하면 편하다.
# https://kosaf04pyh.tistory.com/222

 

11727

num = int(input())
dp = [0]*1001
dp[1]=1
dp[2]=3
for i in range(3, 1001):
    dp[i] = dp[i-1]+ 2*dp[i-2]  # = or ㅁ 두가지 방법으로 채울 수 있으므로 *2를 한다.
print(dp[num]%10007)
# https://jaemin8852.tistory.com/158

 

9095

# 1, 2, 3으로 ★한 개 이상의★ 숫자를 써서 n조합하기
count = int(input())  # 반복할 횟수
for j in range(count) :
    num = int(input())  # 합으로 나타낼 수
    dp = [0]*(num+1)  # n 만큼 리스트 생성, 인덱스는 0부터 시작하므로 n+1
    dp[1:3] = 1,2,4  # 1, 2, 3은 각 1개(1), 2개(11,2), 4(111,12,21,3)개의 경우로 조합 가능
    for i in range(4, num+1) :  # 인덱스3까지는 정해져있으므로 4부터 반복문 시작, 끝은 -1되므로 다시 +1 
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]  # 점화식 : n 앞의 3 숫자의 경우의 수를 모두 합
    print(dp[num])

규칙찾기

n=1, 1가지

1

 

n=2 , 2가지 ( 11 -> 1+1 )

11, 2

 

n=3, 4가지

111, 12, 21, 3

 

n=4, 7가지

1111, 112, 121, 211, 22, 13, 31

 

n=5, 13가지

11111, 1112, 1121, 1211, 2111, 221, 212, 122, 113, 131, 311, 32, 23

 

n=6, 24가지

111111, 11112, 11121, 11211, 12111, 21111, 2211, 1122, 1212, 2121, 1221, 2112, 222, 3111, 1311, 1131, 1113, 123, 213, 231, 321, 312, 132, 33