[백준 BOJ] 9095 1, 2, 3 더하기 python

 

목차

• 1. 문제
• 2. 알고리즘 선택 이유
• 3. 접근방법
• 4. 코드

1. 문제

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

1) 문제

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

 

2) 입력

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

 

3) 출력

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

 

4) 예제 출력

2. 알고리즘 선택 이유

1) 사용한 알고리즘 : dp

2) 이유 : 점화식으로 표현 할 수 있는 문제 

3. 접근방법

- n=1 ~ n=5 정도까지 식을 직접 작성해보며 규칙을 찾는다(점화식)

 

n = 1

(1)

 

n = 2

(1+1),(2)

 

n = 3

(1+1+1),(1+2),(2+1),(3)

 

n = 4

(1+1+1+1),(1+1+2),(1+2+1),(1+3), => 1+(n=3을 만드는 경우) == n=3일 때의 경우의 수 

(2+1+1),(2+2), => 2+(n=2를 만드는 경우) == n=2일 때의 경우의 수

(3+1) => 3+(n=1을 만드는 경우) == n=1일 때의 경우의 수

 

n = 5

(1+1+1+1+1),(1+1+1+2),(1+1+2+1),(1+2+1+1), => 1+(4를 만드는 경우) == n=4일 때의 경우의 수

(2+1+1+1),(2+1+2),(2+2+1),(2+3), => 2+(3을 만드는 경우) == n=3일 때의 경우의 수

(3+1+1),(3+2) => 3+(2를 만드는 경우) == n=2일 때의 경우의 수

 

점화식

- 1,2,3을 사용해서 계산을 해야함으로 n = 1,2,3에 대한 경우의 수를 미리 정의한다

n=1 -> 1

n=2 -> 2

n=3 -> 4

n>=4 -> (n-1 경우의 수) + (n-2 경우의 수) + (n-3 경우의 수)

 

=> (n-1 경우의 수) + (n-2 경우의 수) + (n-3 경우의 수)이 반복되기 때문에 값을 메모리에 저장하고 불러오는 dp 방식이 효율적일듯

 

dp를 초기화 -> 1,2,3일 때의 값을 미리 정의 -> (n-1 경우의 수) + (n-2 경우의 수) + (n-3 경우의 수)를 구한다

 

4. 코드

import sys

tc = int(sys.stdin.readline().strip())

for _ in range(tc):
    n = int(input())

    # 동적 프로그래밍을 위한 dp 배열 초기화
    # 최소길이 4(dp[1]~dp[3]을 미리 지정하기 때문), 최대길이 n+1
    dp = [0] * (4 if n<4 else (n+1))

    dp[1] = 1 # (1) 
    dp[2] = 2 # (1,1), (2)
    dp[3] = 4 # (1,1,1), (1,2),(2,1),(3)

   if n >= 4:
        for i in range(4, n+1):
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3] # 점화식
    
    print(dp[n])