hongjunland

Welcome

1 분 소요

제한

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 128MB 26597 11473 8271 41.550%

문제

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

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

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

틀린 풀이

처음에 일단 단순 재귀호출로 풀어봤습니다. 그러나 시간복잡도가 지수함수로 매우 크기 때문에 시간초과가 떴습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int K;
    static int Cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dfs(0,0);
        System.out.println(Cnt);
    }

    private static void dfs(int d,int sum) {
        if(d==K){
            if(sum==N) Cnt=(Cnt+1)%1000000000;
            return;
        }
        for(int i = 0 ; i <= N ; i++){
            if(sum+i<=N) dfs(d+1,sum+i);
        }
    }
}

풀이

다른 방법을 찾아보기위해서 규칙을 찾아보도록 case를 쭉 적어봤다. 하나씩 나열해보면

(N=0, K=1) ->1 ,(N=0, K=2) ->1 ,(N=0, K=3) ->1, …
(N=1, K=1) =>1 ,(N=1, K=2) ->2 ,(N=1, K=3) ->3, …
(N=2, K=1) =>1 ,(N=2, K=2) ->3 ,(N=2, K=3) ->6, …
(N=3, K=1) =>1 ,(N=2, K=2) ->4 ,(N=2, K=3) ->10, …

쭉 나열해본 결과

f(N,K)= f(N-1,K)+ f(N,K-1) (N=0 일 경우 1)

과 같은 점화식이 도출된다. 그래서 n X k 이차원배열을 만들어서 0번째 행의 1번째 열부터 K까지 1로 초기화한 후에, 1번째 1열부터 N번째 K 까지 점화식을 적용(%1000000000 연산과 같이)한다. 수행이 끝난 뒤에 배열의 N행 K열의 값을 출력한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int K;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[N+1][K+1];
        for(int i = 1 ; i <= K ; i++) dp[0][i] = 1;
        for(int i = 1 ; i <= N ; i++){
            for(int j = 1; j <= K ; j++){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000;
            }
        }
        System.out.println(dp[N][K]);
    }
}

알고리즘 분류

  • 수학
  • 다이나믹 프로그래밍

참고