[백준/Python] 9095 1, 2, 3 더하기

 

📌문제 탐색하기

정수 n(11보다 작은 양수)이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수 구하기

 

알고리즘 선택

n의 범위가 상당히 작기 때문에 효율적인 알고리즘을 고려할 필요는 없다. 다만, n이 4일 때 1, 2, 3의 합으로 나타내는 방법을 구하기 위해 n이 1일 때, n이 2일 때, n이 3일 때의 결과를 이용할 수 있다는 것을 고려한다면, 이 문제는 전형적인 DP(동적 계획법) 문제다. 즉, 작은 문제의 해를 이용해서 큰 문제의 해를 구하는 문제로, 점화식을 세울 수 있어야한다. 

 

DP로 풀 수 있나?

• 중복되는 하위 문제가 있는가?
  • 큰 문제를 작은 문제로 나누었을 때, 작은 문제가 여러 번 사용되는가?
  • 해당 문제는 작은 숫자(1,2,3)를 만드는 방법을 큰 수에 재사용할 수 있다.
• 재귀적 관계, 점화식을 설정 할 수 있는가?
  • 문제를 해결할 때 이전 상태의 값을 이용해 현재 상태의 값을 계산할 수 있는가?
• 결과를 저장하여 재사용할 수 있는 문제인가?
  • 재귀 방식으로 값을 저장하는 memoization이나 반복문으로 테이블을 채우는 tabulation을 사용할 수 있는 방식인가?

 

점화식 세우기

• n=1, 2, 3일 때, 1, 2, 3의 합으로 표현하는 방법의 수는 아래와 같다
  • n=1, 1 => 1
  • n=2, 2 = 1+1 => 2
  • n=3, 3 = 2+1 = 1+2 = 1+1+1 => 4
• n=4일 때, 1,2,3의 합으로 표현하는 방법은 아래와 같다
  • n=1일때 방법 x n=3일 때 방법
  • n=2일 때 방법 x n=2일 때 방법
  • n=3일 때 방법 x n=1일 때 방법
  • 즉, n=4일 때, 방법의 수는 1x1 + 1x2 + 1x4 = 7이다.
• n=5일 때, 1,2,3의 합으로 표현하는 방법은 아래와 같다.
  • n=1일때 방법 x n=4일 때 방법
  • n=2일 때 방법 x n=3일 때 방법
  • n=3일 때 방법 x n=2일 때 방법
  • 즉 n=5일 때 방법의 수는 1x7 + 1x4 + 1x2 = 13이다. 
• 위의 경우를 봤을 때, n=1, n=2, n=3일때 방법의 수는 모두 1이므로 n에서 1, 2, 3 각각을 뺀 수의 방법을 더하면 답이 나오는 것을 알 수 있다.  따라서, n을 1, 2, 3의 합으로 나타내는 방법의 수는 n을 1, 2, 3으로 뺀 수 각각을 1, 2, 3으로 나타내는 방법의 수를 모두 더한 값이다.
• 점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

---

📌 코드 설계하기

1. 1부터 10까지의 수를 1,2,3으로 나타내는 방법의 수를 저장할 리스트 dp를 만든다.
2. 쉽게 답을 알 수 있는 dp[1], dp[2], dp[3]을 각각 1, 2, 4로 저장한다.
3. 테스트 케이스 개수(T)를 입력받는다.
4. i가 4부터 10까지일 때 동안 반복문을 돌면서, dp[i-1]+dp[i-2]+dp[i-3]을 계산하여 dp[i]에 저장한다.
5. 테스트 케이스 개수만큼 n을 입력받고, dp[n]을 출력한다.

 

---

📌 정답 코드

dp = [0,1,2,4] + [0]*7

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

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