[다이나믹 프로그래밍] 9095번 - 1, 2, 3 더하기

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  n = int(input())  # 정수
  d = [0] * 11  # 11보다 작은 양수
  d[1], d[2], d[3] = 1, 2, 4 
  for i in range(4, n + 1):
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

  print(d[n])

[백준] 9095번 - 1, 2, 3 더하기

(한줄평) 아이디어만 떠올린다면 쉽게 풀 수 있는 문제!

풀이 시간: 20분 이내

1) 문제 해결 아이디어

11보다 작은 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다.

DP문제는 보통 아이디어만 잘 떠올리고 점화식을 세운다면 코드 자체는 간결하게 해결할 수 있는 문제가 많은데 이 문제가 그렇다.

 

<n을 1, 2, 3의 합으로 나타내기 위한 3가지 경우의 수>

1. 마지막에 더해진 값이 1인 경우, 1 앞에 더해진 값들의 합은 (n - 1)이다.

2. 마지막에 더해진 값이 2인 경우, 2 앞에 더해진 값들의 합은 (n - 2)이다.

3. 마지막에 더해진 값이 3인 경우, 3 앞에 더해진 값들의 합은 (n - 3)이다.

 

<점화식>

여기서 1, 2, 3의 경우의 수는 아래와 같이 직접 구해서 1, 2, 4로 초기화하였다.

1 = 1

2 = 1 + 1

  = 2

3 = 1 + 1 + 1

  = 1 + 2

  = 2 + 1

  = 3

 

2) 소스코드

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  n = int(input())  # 정수
  d = [0] * 11  # 11보다 작은 양수
  d[1], d[2], d[3] = 1, 2, 4 
  for i in range(4, n + 1):
    # 마지막에 더해진 값이 1, 2, 3인 경우
    d[i] = d[i - 1] + d[i - 2] + d[i - 3]

  print(d[n])