DP: 백준 9095번 문제

1. 문제

각 숫자를 1, 2, 3의 합으로 나타내는 방법의 수를 계산
https://www.acmicpc.net/problem/9095

2. 정답

def count_ways(n):
    # dp[i]는 i를 1, 2, 3의 합으로 나타내는 방법의 수
    dp = [0] * (n + 1)
    
    # 기본 케이스
    dp[0] = 1  # 아무것도 선택하지 않는 경우
    
    # 각 숫자에 대해
    for i in range(1, n + 1):
        # 1을 더하는 경우
        if i >= 1:
            dp[i] += dp[i-1]
        # 2를 더하는 경우
        if i >= 2:
            dp[i] += dp[i-2]
        # 3을 더하는 경우
        if i >= 3:
            dp[i] += dp[i-3]
    
    return dp[n]

def solve():
    # 테스트 케이스 개수 입력
    T = int(input())
    
    # 각 테스트 케이스 처리
    for _ in range(T):
        n = int(input())
        print(count_ways(n))

# 프로그램 실행
if __name__ == "__main__":
    solve()

3. 회고

아니 ;; 진짜 전혀 생각을 못 했었음
무슨 이상한 완전 탐색으로 하려다가 아니 진짜 이건 아닌 것 같아서 답지 봤는데 아 ;;;
진짜 제로부터 시작해서 이거 하나씩 덧붙여나가는 느낌이구나..

이게 다이나믹 프로그래밍이구나 싶었음...

그니까 이 알고리즘을 순서대로 나열해보자면

---

n = 0 일때
[0, 0, 0, 0] 이런식으로 먼저 인덱싱 잡아 놓고

처음 부분에는 dp[0] 일때는 아무것도 선택 안했다고 생각하고 1 로 잡고

---

n = 1 일때

1. dp[0] 을 먼저 거쳐서 1 확보해주고
2. dp[1] 을 만들때 dp[0]에서 1씩 추가한다는 설정으로 경우의수 가져와 주고
3. 아직 2로 넘어가지 못하므로 (1이니까! 2가 나올 수가 없지) 그대로 종료

---

n=2 일때
똑같이
1. dp[0] 거치고
2. dp[1] 을 만들 때 dp[0]에서 1씩 추가한다는 설정으로 경우의 수 가져와 주고
3. dp[2] 을 만들 때 dp[1]에서 1씩 추가한다는 가정으로 경우의수 가져온 다음, 다시 dp[0]에서 2씩 추가한다는 가정으로 경우의수 또 가져와 줌

---

n=3 일때
똑같이
1. dp[0] 거치고
2. dp[1] 을 만들 때 dp[0]에서 1씩 추가한다는 설정으로 경우의 수 가져와 주고
3. dp[2] 을 만들 때 dp[1]에서 1씩 추가한다는 가정으로 경우의수 가져온 다음, 다시 dp[0]에서 2씩 추가한다는 가정으로 경우의수 또 가져와 줌
4. dp[3] 을 만들 때 dp[2]에서 1씩 추가한다는 가정으로 경우의 수 가져오고
다시 dp[1]에서 2씩 추가한다는 가정으로 경우의수 또 가져오고
다시 dp[0]에서 3씩 추가한다는 가정으로 경우의 수 또 가져오고

...

이런식으로 반복... 키야... 이렇게 푸는 구나..

알고리즘을 잘 하면 확실히 문제 해결을 위한 사고의 폭이 넓어지겠다는 생각이 들었다.