1, 2, 3 더하기 ( 9095 번 )

9095번: 1, 2, 3 더하기

 

---

🧠 알고리즘

• DP (Dynamic Programming, 동적 계획법)

 

✔️ 동작 방식

문제 핵심 아이디어

이 문제는 “이전 3개의 결과를 이용해 현재 값을 구하는 DP 점화식” 으로 해결할 수 있다.

1. 초기화
   • dp[1] = 1 → (1)
   • dp[2] = 2 → (1+1, 2)
   • dp[3] = 4 → (1+1+1, 1+2, 2+1, 3)
2. 점화식 계산
   • 4부터 10까지 반복하며
     dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 로 채움.
     → dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7
3. 입력 처리 및 결과 출력
   • 각 테스트 케이스의 입력값 n에 대해 미리 계산된 dp[n]을 출력.

---

 

🧾 코드

import sys

def _cr_case(num):
    """
        각 케이스 경우의 수
        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)
    """
    if num == 1:
        return 1
    elif num == 2:
        return 2
    elif num == 3:
        return 4
    
    dp = [0] * (num + 1)
    dp[1], dp[2], dp[3] = 1, 2, 4
    for i in range(4, num + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    return dp[-1]
    

def _main(n):
    answer = []
    
    for _ in range(n):
        test = int(sys.stdin.readline().rstrip())
        answer.append(_cr_case(test))

    return '\n'.join(map(str, answer))
        
n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for _ in range(t) : 각 테스트 케이스 순회 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )