백준 9095번 1,2,3 더하기

주어진 자연수를 1,2,3으로만 표현했을때 나올수 있는 가지수를 구하는 문제이다 dp문제여서 규칙이 있다고 생각하고 풀었다 조건을 못찾으면 어려운 문제이다

 

조건을 알아내기위해 1붙터 조건을 찾아봤다

• 1 = 1개
• 2 -> 2,11 = 2개
• 3 -> 3,12,21,111 = 4개
• 4 -> 13,31,22,211,121,112,1111 = 7개
• 5 -> 23,32,122,212,221,2111,1211,1121,1112,311,113,131,11111 = 13개
• 6 -> 33,321,312,132,231,213,123,222,3111,1311,1131,1113,2211,2121,2112,1221,1212,1122,11112(5개),111111 = 24개

이렇게 계산을 해보면 4는 1+2+4, 5일 때는 2+4+7 = 13개, 6일 때는 4+7+13=24이므로

i번째는 [i-3] + [i-2] + [i-1] 이란걸 알 수 있다

 

 

import sys
input = sys.stdin.readline   

test = int(input())
arr = [0]*12
arr[1]=1;arr[2]=2;arr[3]=4
for i in range(4,12):
    arr[i] = arr[i-3] + arr[i-2] + arr[i-1]
    
for _ in range(test):
    x = int(input())
    print(arr[x])

입력하는 값의 최대는 11로 설정했다(이제보니 최대 10도 가능) 여러 테스트 케이스마다 계산을 반복한다면 시간이 매우 많이 걸려서 미리 계산해논 배열에 값을 가져오기로 한다