[Algorithm] [Python] 백준/BOJ - 9095 _ 1, 2, 3 더하기

9095 - 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보다 작다.

출력

---

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

제출 코드

---

from sys import stdin

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

t = int(stdin.readline())
for _ in range(t):
    print(solution(int(stdin.readline())))

문제풀이

---

참고로 위 문제는 DP 알고리즘으로 분류되어있다.

일단 문제를 접했을때 정답을 찾아내기 위한 패턴을 알아내기 위해 경우의 수를 살펴봤다.

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), (2,2), (1,3), (3,1) 7개의 방법이 있다.

뭔가 규칙이 보일것 같으면서도 안보인다, 한번 더 살펴보자.

5 = (1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1), (1,2,2), (1,1,3), (1,3,1), (2,1,1,1), (2,1,2), (2,2,1), (2,3), (3,1,1), (3,2) 총 13개의 방법이 있다.

왜 DP로 분류되었는지 느낌이 온다.

만들고자 하는 숫자의 값이 증가하면서 이전의 숫자를 만들기 위해 구성했던 경우의 수가 사용되고 있다.

숫자 1, 2, 3을 갖고 1을 만드는 방법은 1개, 2를 만드는 방법은 2개, 3을 만드는 방법은 4개, 4를 만드는 방법은 7개, 5를 만드는 방법은 13개.

위 패턴이 읽혔다면 아래와 같은 점화식을 도출해낼 수 있다.

F(n) = F(n-1) + F(n-2) + F(n-3) (n > 3)

위 점화식이 문제풀이의 핵심이다.

따라서 1, 2, 3에 대한 예외 처리를 해주고 그 이외의 값은 재귀와 점화식을 통해 값을 도출하는 코드를 작성한다.