[python] 백준 > DP > 1,2,3 더하기

[문제]

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

[나의 풀이]

DP방식

import sys

T = int(sys.stdin.readline())

dq = [0, 1, 2, 4]
for _ in range(T):
    n = int(sys.stdin.readline())
    for i in range(len(dq), n+1):
        dq.append(dq[i-1]+dq[i-2]+dq[i-3])
    print(dq[n])

• dp문제이다.
• dp문제는 일단 패턴을 찾아야 한다.(?)
  • 1 = (1) 1개의 방법
  • 2 = (1,1), (2) 2개의 방법
  • 3 = (1,1,1), (1,2), (2,1), (3) 4개의 방법
  • 4 = (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3), (3,1) 7개의 방법
  • 5 = (1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1), (1,2,2), (1,1,3), (1,3,1), (2,1,1,1), (2,1,2), (2,2,1), (2,3), (3,1,1), (3,2) 13개의 방법
  • 규칙 : n이 3 이상일 때, F(n) = F(n-1) + F(n-2) + F(n-3) 이 핵심이다.

DFS방식

T = int(input())

def dfs(n, number):
    global cnt
    if number == n:
        cnt += 1
        return 0
    elif number > n:
        return 0
    dfs(n, number+1)
    dfs(n, number+2)
    dfs(n, number+3)


for _ in range(T):
    cnt = 0
    n = int(input())
    dfs(n, 0)
    print(cnt)

• dfs로도 가능하다.
• dfs인자로 n과 초깃값(number) 0을 전달해준다.
• n과 number과 같아지는 순간 갯수를 1 증가시킨 뒤 리턴, n보다 number 가 커진 경우에도 return

[다른 사람의 풀이]

import sys
input = sys.stdin.readline
T = int(input())
memo = {1:1, 2:2, 3:4}
def rep(n):
    if memo.get(n):
        return memo[n]
    memo[n] =  rep(n-3) + rep(n-2) + rep(n-1)
    return memo[n]
for _ in range(T):
    n = int(input())
    print(rep(n))