재귀 관계식의 n번째 항을 구하는 C 프로그램 작성법

문제 개요

세 개의 숫자 a, b, c와 값 n이 주어졌을 때, 다음과 같은 재귀 관계식을 따른다고 가정해 보겠습니다.

S(1)은 a를 반환합니다.
S(2)는 b를 반환합니다.
S(3)은 c를 반환합니다.
n > 3인 모든 경우에 S(n)은 S(n-1) + S(n-2) + S(n-3)을 반환합니다.

우리의 목표는 이 재귀 관계식에 따라 n번째 항을 구하는 것입니다.

예시로 이해하기

예를 들어 입력이 a = 5, b = 2, c = 3, n = 6이라면 출력은 28이 됩니다. 그 과정은 다음과 같습니다.

S(4) = S(3) + S(2) + S(1) = 3 + 2 + 5 = 10
S(5) = S(4) + S(3) + S(2) = 10 + 3 + 2 = 15
S(6) = S(5) + S(4) + S(3) = 15 + 10 + 3 = 28

풀이 접근 방법

이 문제를 해결하기 위해 solve()라는 함수를 정의하고, 이 함수가 a, b, c, n 네 개의 매개변수를 받도록 구성합니다.

n이 1이면 a를 반환합니다.
n이 2이면 b를 반환합니다.
n이 3이면 c를 반환합니다.
그 외의 경우에는 solve(a, b, c, n-1) + solve(a, b, c, n-2) + solve(a, b, c, n-3)을 반환합니다.

예제 코드

아래 구현 예시를 통해 더 쉽게 이해할 수 있습니다.

#include <stdio.h>
int solve(int a, int b, int c, int n){
    if(n == 1)
        return a;
    if(n == 2)
        return b;
    if(n == 3)
        return c;
    return solve(a, b, c, n-1) + solve(a, b, c, n-2) + solve(a, b, c, n-3);
}
int main(){
    int a = 5, b = 2, c = 3, n = 6;
    int res = solve(a, b, c, n);
    printf("%d", res);
}

입력

5, 2, 3, 6

출력

참고: 성능 개선 팁

위의 순수 재귀 방식은 같은 값을 중복해서 계산하기 때문에 시간 복잡도가 지수적으로 증가할 수 있습니다. 실전에서는 메모이제이션(memoization)을 활용하거나, 반복문을 사용해 마지막 세 항만 변수로 유지하며 계산하면 O(n)의 선형 시간 복잡도로 최적화할 수 있습니다.