코딩 챌린지 5일차 : 9095번 1, 2, 3 더하기(S3)

9095 : 1, 2, 3 더하기 - 문제 링크

1. 문제 탐색하기

입력

T 테스트케이스의 수
n 조합의 가짓수를 구할 정수

구하고자 하는 것

n의 1, 2, 3 조합의 가짓수. 점화식에서의 A[n]

알고리즘 설계

우선 n = 5까지의 경우의 수를 생각해보면

• A[1] = 1 (초항)
  1
• A[2] = 2 (초항)
  1+1, 2
• A[3] = 4 (초항)
  1+1+1, 2+1, 1+2, 3
• A[4] = 7
  1+1+1+1, 2+1+1, 1+2+1,
  1+1+2, 2+2,
  1+3
• A[5] = 13
  1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 2+2+1, 1+3+1,
  1+1+1+2, 2+1+2, 1+2+2, 3+2,
  1+1+3, 2+3

위와 같은 점화식을 금방 찾을 수 있었다.

경우의 수를 나열하여 보았을 때 n은
n - 1의 모든 경우의 마지막에 1을 더하는 경우,
n - 2의 모든 경우의 마지막에 2를 더하는 경우,
n - 3의 모든 경우의 마지막에 3을 더하는 경우의 합이 된다
(위 경우의 수 굵은 글씨 참조)

처음에는 양쪽에 더해야 하는 것 아닌가? 라는 생각을 했지만
양쪽에 더하게 되면 중복이 발생하게 되므로
마지막(또는 처음)에만 더함

시간복잡도

n > 3일때 n - 3만큼 반복문 수행 -> $O(n)$
0 < n < 11이기 때문에 최대 10번의 계산 수행 => 통과 가능

2. 코드 설계하기

1. input 받기
2. 초항 설정
3. n값에 따른 분기
   • n < 4일 때 바로 결과값 출력
   • 아닐 때 반복문으로 점화식 n - 3회 수행 후 결과값 출력

3. 시도 회차 수정 사항

1회차) 성공! (깨알 1년 전...)

4. 정답 코드

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    one, two, three = 1, 2, 4
    
    # 초항일 때
    if n == 1: 		print(one)
    elif n == 2: 	print(two)
    elif n == 3: 	print(three)
    # 그 이상일 때 점화식 사용
    else:
        for i in range(n - 3):
            one, two, three = two, three, one + two + three
        print(three)

1년 전에 풀었던 문제지만 오랜만에 DP를 템플릿도 써가며 풀어보려니 힘든 점이 있었다. 그 당시에는 규칙만 찾고 코드 작성해서 제출했던 것 같은데 지금은 어떻게 해서 해당 점화식이 나왔는지 생각해볼 수 있어서 의미있는 풀이를 한 기분이다.

5. 해설지 참고 후

• 자정 이후 작성