[Python] 백준 풀기 9095 - 1, 2, 3 더하기

파이썬 백준 9095번

실버3

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

 

 

 

문제 보기

분류: 다이나믹 프로그래밍

 

 

 

 

 

문제 풀기

나열되는 숫자들로 규칙성을 알아본다.

 

1 은 자기 자신 1 만 가능.

2 는 이전 1 에 1 더한것 그리고 자기 자신 2 가능.

3 은 어전전 1 에 2 를 더한것과 1+1 더한것 그리고 이전 2 에 1 을 더한것 그리고 자기 자신 3 가능.

 

4 부터 규칙성이 뚜렷해 진다. 합으로 만들수 있도록 주어진 숫자는 1, 2, 3 세 개 이기 때문에 다음 차례 n 에서는 이전에 계산되었던 합들을 1, 2, 3 의 경우에 맞춰 추가적으로 생각하면 된다.

 

 

이 규칙을 이용하여 코드를 작성해본다.

T 를 입력받고 n 은 11 보다 작기 때문에 모든 10 가지 n 에 대해 모든 결과를 구하고 지정된 n 에 대한 결과 합을 출력한다.

    T = int(inputdata().strip())
    nsum_ls = [None] * 11

 

    for _ in range(T):
        n = int(inputdata().strip())
        print(nsum_ls[n])

 

초기값 n = 1, 2, 3 에 대한 결과를 저장한다.

    nsum_ls[1] = 1
    nsum_ls[2] = 2
    nsum_ls[3] = 4

 

for loop 을 통해 모든 n 에 대한 합의 결과를 각 index 에 맞게 저장한다.

공부 기록겸 두가지 표현을 모두 저장하였다.

    for i in range(4, 11):
        nsum_ls[i] = nsum_ls[i - 3] + nsum_ls[i - 2] + nsum_ls[i - 1]
        nsum_ls[i] = sum(nsum_ls[i-3 : i])

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnOneTwoThree(T, nsum_ls):
    nsum_ls[1] = 1
    nsum_ls[2] = 2
    nsum_ls[3] = 4
    
    for i in range(4, 11):
        nsum_ls[i] = nsum_ls[i - 3] + nsum_ls[i - 2] + nsum_ls[i - 1]
        nsum_ls[i] = sum(nsum_ls[i-3 : i])
        
    return nsum_ls


if __name__ == "__main__":
    T = int(inputdata().strip())
    nsum_ls = [None] * 11
    # print(nsum_ls)         # test print
    
    nsum_ls = fnOneTwoThree(T, nsum_ls)
    # print(nsum_ls)         # test print
    
    for _ in range(T):
        n = int(inputdata().strip())
        print(nsum_ls[n])

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline

def fnOneTwoThree(T, nsum_ls):
    nsum_ls[1] = 1
    nsum_ls[2] = 2
    nsum_ls[3] = 4
    
    for i in range(4, 11):
        nsum_ls[i] = nsum_ls[i - 3] + nsum_ls[i - 2] + nsum_ls[i - 1]
        nsum_ls[i] = sum(nsum_ls[i-3 : i])
        
    return nsum_ls


if __name__ == "__main__":
    T = int(inputdata().strip())
    nsum_ls = [None] * 11
    print(nsum_ls)         # test print
    
    nsum_ls = fnOneTwoThree(T, nsum_ls)
    print(nsum_ls)         # test print
    
    for _ in range(T):
        n = int(inputdata().strip())
        print(nsum_ls[n])



# 3
# 4
# 7
# 10

# [None, None, None, None, None, None, None, None, None, None, None]
# [None, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]

# 7
# 44
# 274