백준 11057 오르막 수 (Java,자바)

이번에 풀어본 문제는
백준 11057번 오르막 수 입니다.

📕 문제 링크

❗️코드

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

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

        dp = new int[N+1][10];
        for(int i = 0; i < 10; i++) dp[1][i] = 1;

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

        int answer = 0;
        for(int i = 0; i < 10; i++)
        {
            answer += dp[N][i];
        }

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

📝 풀이

문제의 조건을 만족하는 오르막 수 들 중 N자릿수의 오르막수의 갯수를 출력하는 문제입니다. 2차원배열 dp는 dp[자릿수][시작값]으로 구성됩니다. 점화식을 구하기 위해 한 자릿수, 두 자릿수 정도 써보시면 점화식을 유추해낼 수 있습니다.

📜 후기

노트에 적으며 직접 점화식을 찾아보면 생각보다 쉽게 구할 수 있는 문제입니다.

좋은 웹페이지 즐겨찾기