[c++] BOJ 2225 :: 합분해

 

난이도 : 골드 5

걸린 시간 : 50분

문제

합분해 문제 바로가기

2225번: 합분해

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

풀이

• 작은 문제 : 현재 남은 N에서 남은 K개로 N을 만들 수 있는 경우의 수
• 재귀 함수 : (N, K) => int 의 형태
  • 사용하는 수 i를 for문 돌면서, j를 1씩 감소시켜서 재귀
  • 종료 조건
    • N이 0일 때는 남은 수가 모두 0인 경우 1가지만 존재
    • K가 0이고 N가 0이 아닐 때 남은 경우의 수 없음 => 0 반환
• DP : N, K를 행, 열로 하고 값이 경우의 수인 2차원 배열 형태

그림으로 표현하자면 이러한 형태이고, 진한 파란색의 부분은 옅은 파랑색 부분의 합이 된다.

 

코드

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

long long memo[201][201];

int returnCase(int N, int K) {
    if (N == 0) {
        // 끝 => 남은 K를 0으로 채우는 하나의 경우 존재
        return 1;
    }
    if (K == 0) {
        // K는 끝났는데 수가 끝나지 않았을 때 => 경우 존재 x
        return 0;
    }
    long long res = 0;
    for (int i = 0; i <= N; i++) {
        if (memo[N - i][K - 1] != -1) {
            res += memo[N - i][K - 1];
            continue;
        }
        memo[N - i][K - 1] = returnCase(N - i, K - 1);
        res += memo[N - i][K - 1];
    }
    return res % 1000000000;
}

int main() {
    // 7시 12분 시작
    // 8시 끝 (50분)

    // 입력 받기
    int N, K;
    cin >> N >> K;

    memset(memo, -1, sizeof(memo));
    int res = returnCase(N, K);
    if (res >= 1000000000)
        cout << res % 1000000000;
    else
        cout << res;
    cin >> N;
}

 

주의할 점

이렇게 큰 수로 나눠서 return 하라고 할 때는 수의 범위를 벗어날 수 있으므로 중간중간 나눠주기!

 

결과