자연수 N의 합 경우의 수

부산에 중견 코딩 테스트 때 나왔던 문제인데 스터디 같이 하시던 분이 부산 가셔서 테스트 보시고 문제 들고 오심.

최대 1000으로 생각한다.

N=4

1+1+1+1

1+1+2

2+2

3+1

#include<stdio.h>

#include<string.h>

#include <chrono>

int N = 4;

long long memo[1001][1001];

using namespace std;

using namespace chrono;

int GetValue(int idx, int sum)

{

if (sum > N)return 0;

if (sum == N) return 1;

if (memo[idx][sum] != -1) return memo[idx][sum];

long long count = 0;

for (int i = idx; i < N; i++)

{

if (sum + i > N) break;

count += GetValue(i, sum + i);

}

return memo[idx][sum] = count;

}

int main()

{

scanf("%d", &N);

long long count = 0;

system_clock::time_point start = system_clock::now();

memset(memo, -1, sizeof(memo));

for(int i=1; i<N;i++)

count += GetValue(i, i);

printf("%lld\n", count);

system_clock::time_point end = system_clock::now();

duration<double> sec = end - start;

printf("%lf", sec);

    return 0;

}