[백준 BOJ_9095] 1, 2, 3 더하기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀었습니다.

cache는 다음과 같습니다.

cache[i] = 1, 2, 3의 합으로 정수 i를 나타낼 수 있는 방법의 수 

4부터 10까지 각각 다음과 같은 세 가지 경우의 수를 더해주면 됩니다.

• i-1를 만들 수 있는 방법에 1을 더하여 i 만들기
• i-2를 만들 수 있는 방법에 2를 더하여 i 만들기
• i-3를 만들 수 있는 방법에 3를 더하여 i 만들기

세 가지 방법을 모두 더한 값을 cache[i]에 저장해준 뒤 cache[n]을 출력해줍니다.

코드

T = int(input())

cache = [0 for _ in range(11)]

cache[1] = 1 # 1
cache[2] = 2 # 1 + 1, 2
cache[3] = 4 # 1 + 1 + 1, 2 + 1, 1 + 2, 3

for i in range(4, 11):
  cache[i] = cache[i-1] + cache[i-2] + cache[i-3]

for _ in range(T):
  n = int(input())
  print(cache[n])