사용 언어: python 3.9.1

❓ Problem

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

📕 피드백

1. 발전 방향

반복되는 패턴을 먼저 찾고
⇒ 재귀함수의 계속조건을 설정
⇒ 재귀함수의 종료조건을 설정
⇒ 메모이제이션 활용(재귀함수에서 구하는 값들이 중복되지 않게(시간적 손실))

🚩 Solution

1. 접근법

재귀적으로 접근 + 메모제이션 이용하는 게 맞다고 생각함.

즉,

4 = 1+3 = 2+2 = 3+1
3 = 1+1+1 = 1+2 = 2+1 = 3
2 = 1+1 = 2
1 = 1

이므로, 어떤 숫자 n에 대해 1,2,3의 합으로 나타내는 방법의 수를 P(n)이라고 할 때

$P(n) = P(n-1) + P(n-2) + P(n-3)$ 이라고 할 수 있다. 물론 이때 n>3라는 제약조건이 있다.

P(0)을 편의상 0으로 설정하고, P(1)=1이므로 그렇게 ways라는 배열에 저장해 둔다.

2. 코드

import sys; read = sys.stdin.readline

def findWays(n):
    if ways[n] != 0:
        return ways[n]
    tot = 0
    for i in range(1, 4 if n>2 else n+1):
        tot += findWays(n-i)
    ways[n] = tot
    return tot

T = int(read())
ways = [1]*2+[0]*9

for _ in range(T):
    n = int(read())
    findWays(n)
    print(ways[n])

3. 결과

시간 복잡도 분석

최악의 경우 O(n)