[브루트스] 백준 15652번 N과 M (4,5,6) (C++)

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

 

음

 

이 문제는 어떤 수 n에 대한 합을 1 ,2,3으로 나타내는 방법에 대한 횟수를 구하는 식이다

하지만 숫자의 순서또한 고려한다.

 

사실 이 식은 점화식이 존재하고 쉽게 구할 수 있다.

 

예를들어 숫자 6을 구할 때

5+1 

4+2

3+3 

이런 방식으로 구해도 되지 않는가?

(마지막 숫자가 1,2,3인경우)

 

그래서 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

으로 매우매우매우쉽게 구할 수 있지만

 

브루트포스 재귀식으로도 한번 구현을 해보겠다.

 

먼저 생각을 해보자

 

1.현재까지의 합을 추적

2. 합이 n이되면 방법수를 +1한다

3. 합이 초과하면 중단

 

우리는 앞서 많은 순열과 관련된 문제들을 풀었고, 이때 사용한것이 백트래킹이다

 

근데 여기서도 합을 초과한 경우 중단하여 백트래킹을 할 수 있지 않은가?

즉 순열에서 사용한 개념을 바탕으로 여기서도 한번 써먹어 보자는 것이다!

 

#include <iostream>

using namespace std;

int f(int sum, int n);

int main()

{

    int n;

    cin >> n;

    int t_n;

    while (n--)

    {

        cin >> t_n;

        cout << f(0, t_n) << "\n";

    }

}

int f(int sum, int n)

{

    if (sum > n)

        return 0;

    if (sum == n)

        return 1;

    return f(sum + 1, n) + f(sum + 2, n) + f(sum + 3, n);

}

 

짜잔

 

return 값은 모든 함수의 숫자 값이다

 

안에 있는 재귀함수들을 본다면

1로 시작할때, 2로시작할떄, 3으로 시작할때로 나뉘어져 있다.

1로 시작하고 , 들어가서 남은 숫자에 대해 1,2,3으로 시작하는 숫자들을 다 더하고, 아니면 0으로 ~

 

dp식을 사용한 방법은 나중에 또 글로 쓸 것이다.