백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA)

문제 : boj2688

 

 

방법 1. dp로 풀기

  dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다.

 

그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다.

 

거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[n][9] 를 더해서 출력해주면 답을 구할 수 있다.

 

방법1 코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private long[][] dp = new long[65][11];

    private void initDp() {
        Arrays.fill(dp[1], 1);
        for (int i = 2; i <= 64; i++) {
            for (int j = 1; j <= 10; j++) {
                dp[i][j] += dp[i-1][j] + dp[i][j-1];
            }
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        initDp();
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            int n = Integer.parseInt(br.readLine());
            long sum = 0;
            for (int i = 1; i <= 10; i++) {
                sum += dp[n][i];
            }
            sb.append(sum).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

 

방법 2. 중복조합 공식으로 풀기

  원래 dp로 풀었으나, 수학으로도 풀린다는 문선생님(?)의 가르침을 받음. 결국 10가지 수에서 중복을 허용한 상태로 입력으로 들어온 n가지를 선택하면 되는 문제이므로 중복조합 공식 nHr 을 적용하면 풀 수 있음. 수학이 약한 나로써는 dp가 더 쉽긴 했음.

  이고 위 수식에서 n은 이 문제에서 10으로 고정이고, r은 입력으로 들어오는 T개의 n에 해당한다. 그리고 nCr = nCn-r 이라는 공식 까지 합쳐줘서 풀면 수식으로 이 문제를 풀 수 있음.

 

방법2 코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            int r = Integer.parseInt(br.readLine());
            int n = 10+r-1;
            r = Math.min(r, n-r);

            long tmp = 1;
            for (int i = 0; i < r; i++) tmp*=n--;
            for (int i = 2; i <= r; i++) tmp/=i;
            sb.append(tmp).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}