[백준 알고리즘] 9095번 Python 풀이

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

 

 

백준 알고리즘 9095번

 

지문도 짧고 간결한 문제인데, 풀이에는 애를 먹었다.

결국 지지고볶다가 다른 분의 풀이를 참고해 풀게 되었는데 1, 2, 3의 합으로 나타내는 방법에 규칙성이 있었다.

1 = 1 ->(1가지)
2 = 1 + 1,    2 -> (2가지)
3 = 1 + 1 + 1,   1 + 2,    2 + 1,    3 -> (4가지)
4 = 1 + 1 + 1 + 1,    1 + 2 + 1,    2 + 1 + 1,    3 + 1,    1 + 1 + 2,    2 + 2,    1 + 3 -> (7가지)

값을 N이라고 할 때, 4부터는 N-1의 +1, N-2의 +2, N-3의 +3으로 표시할 수 있다.
따라서 해당 N을 1, 2, 3의 합으로 만드는 방법은 (N-1의 방법의 수) + (N-2의 방법의 수) + (N-3의 방법의 수)로 구할 수 있다.

import sys
t = int(sys.stdin.readline())

# 1, 2, 3의 합으로 나타내는 방법의 수를 담는 리스트
s = [1, 2, 4]

# n은 11보다 작다는 조건이 있어, 미리 계산해 저장
for i in range(3, 11):
    s.append(s[i-1]+s[i-2]+s[i-3])

for i in range(t):
    n = int(sys.stdin.readline())
    print(s[n-1])