재귀 알고리즘 구현 by Python

 

문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음,

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오.

 

출처: ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001

 

문제를 읽자 마자, 피보나치 수열(1,1,2,3,5,8....) 처럼 각 정수 1부터 n까지 관계가 있을거같은 느낌이 강력하게 드는 문제였다.

 

f(n)을 n일때 나타낼 수 있는 방법의 수라고하자.

 

패드에 숫자 1~5까지 일일이 적어보며 방법의 수를 찾고 규칙을 찾았다, 바로 f(n) = f(n-1) + f(n-2) + f(n-3)인 것이다...

 

f(1) = 1

f(2) = 2

f(3) = 4

f(4) = 7 = (1+2+4)

f(5) = 13 = (2+4+7)

 

위 규칙만 찾게되면, 코드로 구현함을 그리 어렵지 않았다.

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

결과를 확인해 보면,

print('f(5):{0}, f(8):{1}'.format(numOfSum(5),numOfSum(8)))

그림 - 1 결과값

정상 작동함을 알 수 있다.