[알고리즘] 백준 파이썬 9095 1,2,3 더하기

📍 문제 탐색하기

이번 문제는 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 계산하는 문제이다. 이를 동적 계획법(DP)을 사용해 효율적으로 해결할 수 있다.

문제 조건

1. 정수 n(1 ≤ n ≤ 10)을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다.
2. 테스트 케이스 개수 T가 주어지고, 각 테스트 케이스에 대해 결과를 출력한다.
3. 예를 들어, n = 4라면 결과는 다음과 같습니다:
   • 1 + 1 + 1 + 1
   • 1 + 1 + 2
   • 1 + 2 + 1
   • 2 + 1 + 1
   • 2 + 2
   • 1 + 3
   • 3 + 1
     → 총 7가지.

---

입력 범위

• 1 ≤ T ≤ 10 (테스트 케이스 개수)
• 1 ≤ n ≤ 10 (계산할 정수)

---

가능한 시간 복잡도

• 최대 n = 10이므로, 동적 계획법(DP)을 사용하면 O(n)으로 해결 가능하다.
• 최대 테스트 케이스가 T = 10이므로, 전체 복잡도는 O(T × n) = O(100)으로 충분히 처리 가능하다.

---

📍 코드 설계하기

입력 처리

1. 테스트 케이스 개수 T를 입력받는다.
2. 각 테스트 케이스에서 계산할 정수 n을 입력받는다.

DP 배열 초기화

1. hap 배열을 초기화하여 각 hap[n]에 n을 1, 2, 3의 합으로 나타내는 방법의 수를 저장한다.
2. 초기값:
   • hap[1] = 1 (1)
   • hap[2] = 2 (1+1, 2)
   • hap[3] = 4 (1+1+1, 1+2, 2+1, 3)

DP 점화식

• hap[n] = hap[n-1] + hap[n-2] + hap[n-3]
  • 마지막에 더해지는 숫자가 각각 1, 2, 3일 때의 경우의 수를 합친다.

결과 출력

• 각 테스트 케이스에 대해 hap[n] 값을 출력한다.

---

📍 시도 회차 및 수정 사항

1차 시도 (틀림) ❌

T=int(input())

hap=[0]*11

for i in range(T):
    n=int(input())

    if n==1:
        hap[1]=1
    elif n==2:
        hap[2]=2
    elif n==3:
        hap[3]=4
    else:
        hap[n]=hap[n-1]+hap[n-2]+hap[n-3]

    print(hap[n])

문제점:

• hap[n] 계산 시, 이전 값(hap[n-1], hap[n-2], hap[n-3])이 미리 계산되어 있지 않을 수 있다.
• 테스트 케이스마다 hap 값을 올바르게 초기화하거나 순차적으로 계산하지 않았기 때문에 올바른 결과가 나오지 않았다.

---

2차 시도 (맞음) ✅

T = int(input())

hap = [0] * 11

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

    for i in range(1, n + 1):  # 순차적으로 1부터 n까지 계산
        if i == 1:
            hap[1] = 1
        elif i == 2:
            hap[2] = 2
        elif i == 3:
            hap[3] = 4
        else:
            hap[i] = hap[i-1] + hap[i-2] + hap[i-3]

    print(hap[n])

hap 값 계산을 순차적으로 수행하도록 수정해주었따.

• for i in range(1, n + 1)을 사용하여 필요한 값(hap[1], ..., hap[n])을 순차적으로 계산해주었다.
• 이로써 테스트 케이스마다 hap 값을 재사용할 수 있고, n값에 대해 항상 정확한 결과를 출력할 수 있게 되었다!

---

📍 느낀점

1. 동적 계획법에서 이전 값이 필요하다는 점을 항상 유의하자!
2. 문제의 조건과 초기값(hap[1], hap[2], hap[3])을 정확히 이해하자!