백준 9095번 1,2,3 더하기 | py 풀이

백준 문제 바로가기

실버1

2주동안 BFS/DFS 문제를 쉬운 것 부터 풀어보고 실버 -> 골드까지 풀어볼 예정이다.

먼저 해당 유형의 기본 문제를 풀어보자.

 

 

 

문제

# 문제

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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

# 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

# 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

풀이

Top-down 풀이

 

dp 딕셔너리 구조를 사용한다.

N을 나타내는 방법의 수를 구하려면 (N-1) + (N-2) + (N-3)을 구해야한다.

초기식은 3까지 구해놓는다.

import sys
input = sys.stdin.readline

#갯수 입력
N = int(input())

#Top-dowm
memo = {}

def dfs(K) :
  #base case
  if K == 1 : return 1
  if K == 2 : return 2
  if K == 3 : return 4

  #memo
  if K in memo:
    return memo[K]

  #memoization
  if K not in memo:
    memo[K] = dfs(K-1) + dfs(K-2) + dfs(K-3)
    return memo[K]
  
for _ in range(N):
  K = int(input())
  print(dfs(K))

 

 

 

bottom-up 풀이

dp[] 배열 자료구조를 사용한다. 탑다운은 필요한 것만 계산하되 느리지만, 바텀업은 전부를 계산하되 빠르다. 이 문제는 최대가 10이므로 이 방법이 더 적절할 수 있다.

 

빈 배열을 크기에 맞게 먼저 선언한다

dp[3]까지 초기식에 값을 넣어준다.

점화식 - 범위의 수를 미리 다 계산한다.

이후에 바로 찾아서 리턴한다.

#갯수 입력
N = int(input())

#배열
dp = [0] * 11

#초기식
dp[1] = 1
dp[2] = 2
dp[3] = 4

#점화식 - 미리 다 계산
for i in range(4, 11) :
  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for _ in range(N) :
  k = int(input())
  print(dp[k])