[백준 9095 : PYTHON] 1, 2, 3 더하기

문제 풀기 : 9095번

9095번: 1, 2, 3 더하기

문제

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다.

(0 < n < 11)

문제풀이

모든 경우의 수를 전부 찾는 완전탐색 문제이다.

• 1 : 1 (1개)

• 2 : 1+1 / 2 (2개)

• 3 : 1+1+1 / 1+2, 2+1 / 3 (4개)

• 4 : 1+1+1+1 / 1+1+2, 1+2+1, 2+1+1 / 2+2 / 1+3, 3+1 (7개)

• 5 : 1+1+1+1+1 / 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1 / 1+2+2, 2+1+2, 2+2+1 / 1+1+3, 1+3+1, 3+1+1 / 2+3, 3+2 (13개)

• 6 : (생략) (24개)

경우의 수를 따져보면 4부터는 규칙이 보인다.

앞의 3개의 숫자들의 방법의 수를 합한 값이 방법의 수가 된다.

예를 들어 4의 방법의 수는 1~3의 방법의 수의 합이 된다.

1 ~ 3일 경우는 미리 계산을 해두어 배열에 넣어놓고 나머지 값들은 4부터 n까지 차례로 방법의 수를 계산한 다음 값을 리턴한다.

 

전체코드

import sys

# 방법의 수 계산
def sol(n):
    # n이 1 ~ 3일 경우 미리 계산해둔 값을 리턴
    if n < 4:
        return data[n]
    else:
        # n이 4이상일 경우 4 ~ n까지 방법의 수를 구함 
        for c in range(4, n+1):
            data[c] = data[c-1] + data[c-2] + data[c-3]
    return data[n]


# 입력
t = int(sys.stdin.readline())
# 0 < n < 11
data = [0, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0]


for i in range(t):
    n = int(sys.stdin.readline())

    print(sol(n))

 

DP로 생각하고 풀었을 때의 코드(위와 풀이법은 동일)

import sys
input = sys.stdin.readline

T = int(input())
for t in range(T):
    n = int(input())
    dp = [0] * 12

    # 초기값 지정
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    # 점화식에 따른 경우의 수 계산
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

    print(dp[n]%10007)