[알고리즘] 백준 9095 (파이썬 풀이)

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

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의 합으로 나타내는 방법의 수를 출력한다.

 

해결코드

t = int(input())
def plus(num):
    if num==1:
        return 1
    elif num==2:
        return 2
    elif num==3:
        return 4
    else:
        return plus(num-1) + plus(num-2) + plus(num-3)

for i in range(t):
    num = int(input())
    print(plus(num))

문제풀이

문제 해결 방법은 수가 커짐에 따라 생기는 규칙을 이용하여 점화식을 사용하였다.

수가 1일 때 경우의 수는 1

수가 2일 때 경우의 수는 2

수가 3일 때 경우의 수는 4

수가 4일 때 경우의 수는 7

수가 5일 때 경우의 수는 13...

이런 식으로 진행이 되는데 수가 5일때 경우의 수는 수가 2,3,4일때 경우의 수를 모두 합한 값이다.

수가 4일 때 경우의 수는 수가 1,2,3일 때 경우의 수를 모두 합한 값이다.

이를 통해 plus함수를 사용하면 점화식이

plus(num) = plus(num-1) + plus(num-2) + plus(num-3)  <-- 이렇게 된다.

다만 num값이 1,2,3일 때는 규칙이 적용되지 않아서 따로 if문으로 설정해주어야 한다.