[Python] BOJ/백준 9095번 1, 2, 3 더하기

[문제]

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

9095번: 1, 2, 3 더하기

 

 

[풀이]

이 문제는 동적 프로그래밍으로 풀어야 하는 문제이다.

동적 프로그래밍의 개발절차는

1. 문제의 사례에 대해 해답을 주는 재귀 관계식 정립
2. 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례 해결

개발절차에 따르면 재귀 관계식을 정립해야 하기 때문에 우선 숫자 사이에서 규칙을 찾아보기로 했다.

5까지 직접 계산해 규칙을 찾아보니 이전 3개의 결과를 더한 숫자가 해당 숫자의 답이 되는 것을 발견했다.

이를 이용해 검증하기 위해 문제 예제에서 나온 7을 위의 규칙으로 계산해보니 44가 나와 문제에 나온 결과와 같았다.  

 

이제 결과를 찾았으니 상향식 방법으로 문제를 해결해야 한다. 동적 프로그래밍의 주된 개념은 "이미 풀어서 답을 알고 있는 부분의 결과가 다시 필요한 경우에는 반복 계산하는 대신 이미 계산된 결과를 사용한다."는 것이다.

 

1, 2, 3만 이용해서 더하기를 해야 하기 때문에 n이 1일 때, 2일 때, 3일 때의 결과는 return 값에 넣어주고, n이 그보다 더 큰 숫자일 경우 위의 규칙에서 찾았던 (3번째 전 숫자의 결괏값 + 2번째 전 숫자의 결과값 + 1번째 전 숫자의 결과값) 이 해당 숫자의 답이 된다.

 

[코드]

import sys

def plus(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return plus(n-3) + plus(n-2) + plus(n-1)

if __name__ == '__main__':
    for _ in range(int(sys.stdin.readline())):
        n = int(sys.stdin.readline())
        print(plus(n))