BOJ 9095 - 1, 2, 3 더하기 (Python3)

백준에는 많은 시리즈 문제들이 존재한다.

아주 다양한 방법으로 별을 찍는 별 찍기 시리즈라거나, 다이나믹 프로그래밍의 진수를 보여주는 돌 게임 시리즈(그 중 두 문제는 이미 다룬 바 있다. 9655번 문제라거나 9659번 문제.), 초보적인 구현 능력을 키우는 골뱅이 찍기 시리즈.

그리고 이 문제로부터 시작되는 다이나믹 프로그래밍의 기초체력을 길러 주는 1, 2, 3 더하기 시리즈가 있다.

이게 다이나믹 프로그래밍의 문제이긴 하지만, 수가 좀 적은가? 재귀 함수의 방법으로 풀어보고자 한다.

원래 하라는 대로 안 하는 게 가장 재미있는 법이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

예제 입력)

3
4
7
10

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

예제 출력)

7
44
274

 

---

내 코드

def f(n):
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    if n > 3: return f(n-1) + f(n-2) + f(n-3)
for _ in range(int(input())):
    print(f(int(input())))

 

다이나믹 프로그래밍이었다면 우선 배열부터 선언하고 보았겠지만, 이번에는 재귀적 함수로 접근한다고 했었다.

n이 3보다 크다면, n을 1, 2, 3의 합으로 나타내는 것은 맨 마지막 숫자에 따라서 갈라질 것이다.

(n-1을 1, 2, 3의 합으로 나타냄)+1, (n-2을 1, 2, 3의 합으로 나타냄)+2, (n-3을 1, 2, 3의 합으로 나타냄)+3의 모양으로 말이다.

그러면, n을 1, 2, 3의 합으로 나타내는 경우의 수를 f(n)으로 둘 때, f(n)은 f(n-1)+f(n-2)+f(n-3)으로 주어지게 되는 것이다.

이게 재귀함수 안쪽에 들어있는 식의 정체이다.

 

이제 더 알아야 하는 정보는 f(1), f(2), f(3)인데, 각각 1, 2, 4의 값을 가짐을 직접 써 봄으로서 쉽게 알 수 있다.

• 1
• 1+1, 2
• 1+1+1, 1+2, 2+1, 3

 

이로서 9095번의 풀이를 마친다.

 

그럼, 오늘도 당신의 코딩 실력이 상승하기를.