[백준] 9095번: 1, 2, 3 더하기(python)

📌 문제 정의

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

9095번: 1, 2, 3 더하기

---

🗒 풀이

1) 재귀 + 점화식 이용

def LRR(num):
    # Linear Recurrence Relations
    if num == 1:
        return 1
    elif num == 2:
        return 2
    elif num == 3:
        return 4
    else:
        return LRR(num - 1) + LRR(num - 2) + LRR(num - 3)


T = int(input())
for _ in range(T):
    n = int(input())
    print(LRR(n))

점화식을 쳐봤더니 Linear Recurrence Relations이라는 번역이 나와서, LRR이라는 함수명으로 지정했다.

일단 이 문제를 풀려고 봤는데 잘 모르겠어서 연습장에 문제 예시를 막 끄적여봤다.

밑의 텍스트는 내가 연습장에 쓴 것들을 타이핑 한 것이다.

점화식 = 수열의 각 항들끼리의 성립하는 관계

피보나치가 a_n+2 = a_n+1 + a_n

1 1 2 3 5 8 13 21 34 …(a_0=0, a_1=1)

1 = (1) = 1
2 = (1,1) (2)  = 2
3 = 1,1,1 ; 1,2 ; 2,1; 3 = 4
4 = 1,1,1,1; 1,1,2; 1,2,1; 2,1,1; 3,1; 1,3; 2,2 = 7
5 = 1,1,1,1,1; 1,1,1,2, ; 1,1,2,1; 1,2,1,1; 2,1,1,1; 3,2; 2,3; 1,1,3; 1,3,1; 3,1,1; 1,2,2; 2,1,2; 2,2,1 = 13
6 = 1,1,1,1,1,1(1) ; 1,1,1,1,2 (5) 1,1,1,3 (4) 2,2,2(1); 3,3(1); 1,1,2,2; 1,2,1,2 ;1,2,2,1 ;2,1,2,1 ; 2,1,1,2; 2,2,1,1; (6)
1,2,3 132 213 231 312 321 (6) = 24 = 13 7 4 = 24

쓰다보니 일정한 규칙이 있는 것을 알았고, 3개씩 더하는 피보나치 수열이라는 것을 알았다. 이 구한 것들을 토대로 총 몇개의 경우의 수가 있는지 알아냈다.

 

 

2) 동적 계획법

이 방법은 스터디 같이 하던 친구가 했던 방법인데, 이렇게도 풀어보고 싶어서 한번 더 풀어봤다.

import sys

input = sys.stdin.readline

ans = [0] * 11  # 입력받은 정수는 11 미만이므로
ans[1] = 1
ans[2] = 2
ans[3] = 4

for i in range(4, 11):
    ans[i] = sum(ans[i-3:i])

T = int(input())
for _ in range(T):
    print(ans[int(input())])

일단 문제에서 입력받은 정수는 11 미만이므로  ans 배열 변수를 미리 만들어놓는다.

다음 1, 2, 3의 값은 1, 2, 4라는 것을 알고 있으니 미리 지정한다. 이는 재귀함수로 코드를 짤 때와 같다.(위의 텍스트 참고)

그리고 말했듯이 3개의 피보나치 배열이라는 것을 아니, 3개 단위로 묶어 i부터 이전 3개의 합산을 각 배열에 넣어준다.

그 다음 입력받은 값들의 해당 인덱스 값을 반환해주면 된다.

---

🤔 후기

이건 그래도 손으로 끄적이면서 확실한 규칙을 찾아 더 재밌게 풀 수 있었다.