[Java] 백준 11057 오르막 수

11057 오르막 수 문제 링크

문제

#1

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        if (N == 1) System.out.println(10);
        else {
            long[][] dp = new long[N][10];
            for (int i = 0; i < 10; i++) {
                dp[0][i] = 10 - i;
            }

            for (int i = 1; i < N-1; i++) {
                for (int a = 9; a >= 0; a--) {
                    for (int j = 9; j >= a; j--) {
                        dp[i][a] += dp[i - 1][j]%10007;
                    }
                }
            }

            long answer = 0;
            for (int i = 0; i < 10; i++) {
                answer += dp[N - 2][i]%10007;
            }

            System.out.println(answer%10007);
        }
    }
}

• 3중 for문이지만.. 맞음..
  • for문 2개가 9번도 안 돌아가는 for문이라 시간초과는 안 난듯
• 규칙성을 찾아서 돌림
  • 첫 번째 경우의 수 배열을 구하면
  • 이후로는 해당 수의 전까지 나왔던 경우의 수를 다 더하는.. 방식..

#2

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int[][] dp = new int[N+1][11];
        Arrays.fill(dp[0], 1);

        for (int i=1; i<=N; i++) {
            dp[i][0] = 1;
            for (int j=1; j<10; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) %10007;
            }

        }

        System.out.println(dp[N][9]);
    }
}

• 수댕 코드가 좋아보여서 참고하고 다시 풀음
  
  
• 시간상 큰 차이는 없음
• 근데 내 코드를 보면 dp를 구하면서 어짜피 answer에 해당하는 값을 구하게 되어 있는데 굳이 answer를 선언해서 같은 코드를 두 번 작성함. -> 수정
  • 메모리 절약, 코드 줄임
• 내 코드 3중 for문 중 마지막 for문은 이전 값들을 더하는데 사용됨. 근데 생각해보면 이전 수가 그 전 값들을 다 더한 값인데 이걸 다시 할 필요가 없음.. 그래서 for문 대신 dp[i-1][j] + dp[i][j-1]로 수정
  • 3중 for문이 2중 for문으로 줄음
  • 수가 9가지라서 시간에 큰 차이가 없는데 경우의 수가 더 많았을 경우 시간이 훨씬 절약될 수 있음