[파이썬/Python] 백준 9095번: 1, 2, 3 더하기

📌 문제 : 백준 9095번

---

📌 문제 탐색하기

n : 정수 $(1 ≤ n ≤ 11)$

입력받은 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.

문제 풀이

1, 2, 3의 조합으로 정수를 나타낼 수 있는 방법의 수를 계산할 때 어떠한 규칙이 있는지 예제를 통해 알아본다.

예제 1) n = 1 → 1가지

• 1

예제 2) n = 2 → 2가지

• 1 + 1
• 2

예제 3) n = 3 → 4가지

• 1 + 1 + 1
• 1 + 2
• 2 + 1
• 3

예제 4) n = 4 → 7가지

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2
• 1 + 3
• 3 + 1

예제 5) n = 5 → 13가지

• 1 + 1 + 1 + 1 + 1
• 1 + 1 + 2 + 1
• 1 + 2 + 1 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 2
• 2 + 2 + 1
• 2 + 1 + 2
• 1 + 2 + 2
• 1 + 3 + 1
• 3 + 1 + 1
• 1 + 1 + 3
• 3 + 2
• 2 + 3

예제6) n = 6 → 24가지

• 1 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 2 + 1 + 1
• 1 + 2 + 1 + 1 + 1
• 2 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 2 + 1
• 1 + 1 + 1 + 1 + 2
• 2 + 2 + 1 + 1
• 2 + 1 + 2 + 1
• 1 + 2 + 2 + 1
• 2 + 1 + 1 + 2
• 1 + 2 + 1 + 2
• 1 + 1 + 2 + 2
• 1 + 3 + 1 + 1
• 3 + 1 + 1 + 1
• 1 + 1 + 3 + 1
• 1 + 1 + 1 + 3
• 1 + 2 + 3
• 1 + 3 + 2
• 2 + 1 + 3
• 2 + 3 + 1
• 3 + 1 + 2
• 3 + 2 + 1
• 2 + 2 + 2
• 3 + 3

위의 예제를 통해 n이 커질수록 이전의 n들의 가짓수의 합에 영향을 받는다는 것을 확인할 수 있었다.
n = 4일 때부터 이전 n들의 경우의 수를 모두 합하면 해당 n의 경우의 수를 구할 수 있다.

이를 활용해 점화식을 세워 DP로 해결하면 될 것이다.
→ dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

n의 최댓값에서 1 큰 크기의 DP 테이블을 정의하고 1부터 n까지의 경우의 수를 구함으로써 원하는 답을 인덱스 n에서 구할 수 있도록 한다.

가능한 시간복잡도

n의 최대 크기만큼 점화식 계산해 dp 테이블 채우기 → $O(1)$
테스트케이스만큼 반복 → $O(T)$

최종 시간복잡도
테스트케이스를 고려하지 않는다면 최악의 경우 $O(11)$로 상수 시간내 계산이 가능하다.

알고리즘 선택

n의 최대 크기만큼 점화식에 따라 경우의 수 계산하는 DP 사용하기

---

📌 코드 설계하기

1. 필요한 입력 받기
2. 테스트케이스 별 반복
3. dp 테이블 정의
4. 테이블 초기화
5. 점화식 따라 테이블 채우기
6. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 테스트케이스 입력
T = int(input())

for _ in range(T):
    # 정수 입력
    n = int(input())

    # dp 테이블 정의
    dp = [0] * 12

    # 점화식 초기화
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    # 그 이상은 점화식 통해 값 채우기
    for i in range(4, 11):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

    # 결과 출력
    print(dp[n])

• 결과