[백준BOJ] 9095번 1, 2, 3 더하기.py

 

백준 저지에서 1,2,3 더하기를 파이썬을 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

9095번 1, 2, 3 더하기.py

tomy9729/Algorithm

 

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

 

설명

정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다. 먼저 1,2,3 각각의 대한 방법의 수를 구해보자.

 

1일 때는 1 하나뿐이다.

 

2일 때는 1+1, 2 두 개이다.

 

3일 때는 1+1+1, 1+2, 2+1, 3 이렇게 총 네 개다. 

 

4일 때는 어떻게 구할까? 4에 대해서 1,2,3을 각각 하나씩 넣는다고 했을 때 다음과 같이 구할 수 있다.

• 1+3
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 1+3
  • -> 4개
• 2+2
  • 2+1+1
  • 2+2
  • -> 2개
• 3+1
  • 3+1
  • ->1개

각각에 대해서 4개, 2개, 1개이며 이는 각각 3을 구할 때, 2를 구할 때, 1을 구할 때의 방법의 수와 같다. 즉 어떠한 수 n에 대한 방법의 수를 구하여 dp [n]에 저장한다고할 때 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]라는 점화식을 구할 수 있다.

n	1	2	3	4	5	6	7	8	...
dp	1	2	4	7	13	24	44	81	...

 

이 문제의 경우 n <=1이므로 반복문을 통해 직접 전부를 구했지만 n이 보다 큰 숫자라면 위 점화식을 통해 재귀 함수나 동적 계획법을 통해 풀 수 있다.

 

코드

#9095번 1, 2, 3 더하기.py
if __name__ == "__main__":
  dp = [0]*12
  dp[0] = 1
  dp[1] = 2
  dp[2] = 4
  for i in range(3,12) : 
    dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
  t = int(input())
  for i in range(t) : 
    n = int(input())
    print(dp[n-1])