[9095번] 1,2,3 더하기

[문제] 정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

[예제입력]

3 (테스트 케이스)

4

7

10

[예제출력]

7

44

274

[풀이를 위한 개념]

재귀함수란 A함수 안에서 A함수를 다시 호출하는 함수를 말합니다. 즉, 자기자신을 다시 호출하는 함수입니다.

#include<iostream>
 
 
using namespace std;
 
void Hello()
{
    cout<<"Hello"<<endl;
    Hello();
}
 
int main()
{
    Hello();
 
    return 0;
}

위의 코드를 보면 Hello() 라는 함수안에 Hello()라는 함수를 다시 불러옵니다. Hello() 같은 함수를 재귀함수라고 부릅니다. 

특별히 함수를 종료시키는 조건이 없으므로 무한으로 반복됩니다.

[그림1] 재귀함수가 호출되는 과정

이렇게 조건 없이 무한으로 반복 되다 보면 stack overflow(스택 넘침현상)라는 오류가 생기게 됩니다.

함수는 스택으로 저장되고 종료조건을 걸지 않으면 함수가 종료되지 않기 때문에 다음 함수를 다음 스택에 차례로 계속 쌓게 됩니다. 사용할 수 있는 스택은 정해져 있기 때문에 (컴퓨터 사양에 따라 다르다) stack overflow라는 오류가 나타납니다.

재귀함수는 직관적이라는 장점을 가지고 있지만 수학적으로 재귀 과정을 줄이지 못하면 메모리 초과와 같은 한계를 많이 드러내게 됩니다.

[풀이과정]

트리로 그려보면 문제를 쉽게 이해할 수 있습니다. 예제입력이 4일 때를 트리 그래프로 어떻게 답이 나오는지 그려보겠습니다.

[그림2] 빨간색 원은 답(합이 4)이 나오는 과정의 마지막 부분이다.

이 트리를 보면 왜 재귀로 풀면 쉽게 구현할 수 있는지 알 수 있습니다. 모든 node에 1,2,3을 더한 값의 갈래로 뻗어나가기 때문입니다. 즉, 같은 함수를 함수 안에서 계속 반복해서 사용할 수 있다는 뜻입니다.

사실 이 과정은 DFS의 과정입니다. 답 4가 만족할 때까지 계속 파고들고 답이 나오거나 나오지 않을 때는 거슬러 올라가 다른 node를 방문하죠. DFS의 정의 자체가 재귀이기 때문에 재귀함수를 사용해서 풀 수 있습니다. (stack overflow 때문에 stack을 직접 사용해서 구현하는게 대다수지만..)

어찌됐든 [그림 2]를 통해서 빨간 원을 그리기 위해서는 경로를 통해서 온 값들의 합이 4이고, 최종답을 얻기 위해선 빨간색 원의 개수를 구하면 됩니다.

모든 node에서 1,2,3 씩 더하면서 여태까지 더해졌던 값이 4가 될 때, 1을 return 하고 모든 return 값을 출력하면 답을 얻을 수 있습니다.

[정답]

#include<iostream>
 
 
using namespace std;
 
 
int func(int count, int sum, int result)
{
    if(count > 10) return 0;
    if(sum > result) return 0;
    if(sum == result) return 1;
 
    int now = 0;
    for(int i = 1; i<=3 ; i++)
    {
        now = now + func(count+1, sum+i, result);
    }
 
    return now;
 
}
 
 
int main()
{
    int t;
    int n;
 
    cin >> t;
 
    while(t--)
    {
        cin >> n;
 
        cout << func(0,0,n) << endl;
    }
}

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다 

 

1. 총 세가지의 문제 풀이 방법 중 선택할 수 있다.

첫번째는, N중 for문으로 전부 다해보기. (매번 노드마다 1,2,3 루프를 돌려 더하면서 조건에 만족하면 출력할 수 있다.)

두번째는, stack을 이용한 DFS.

세번째는, 재귀를 이용한 DFS.

2. 아직까지 재귀함수를 정확하게 머릿속에 그려내는 훈련이 되어있지 않다. 코드를 보고 재귀함수가 돌아가는 과정을 떠올릴 수 있지만 그 반대가 안됨.. 

그냥 재귀함수를 임의로 전부다 펼쳐놓고 아래부터 풀어나간다고 생각하자( 제일 아래는 조건에 걸리는 부분이겠지)