요즘 좋은 일과 나쁜 일이 겹치면서 PS 포스팅이 미뤄졌다...
이제 다시 시작하는 마음으로 꾸준히 최선을 다해야겠다🙃

📝문제

수의 길이가 입력됐을 때 만들 수 있는 오르막 수의 개수를 출력하는 문제이다.
최대 개수를 찾는 문제이므로 DP를 써서 풀어야겠다고 생각했다.

수의 길이 N을 입력 받을 때 1~N 범위를 iteration하며
dp[i][j] : 수의 길이가 i 일 때 숫자 j가 1의 자리 수인 것의 개수
를 찾는다.

• dp[0][0~N] = 0
• dp[1][0~N] = 1 // 0, 1, 2,,,, 9
• dp[1~N][0] = 1 // 0, 00, 000, 0000,,,,

위의 방식으로 초기화를 해둔 후,
이후의 점화식은
dp[i][j] = dp[i][j-1] + dp[i-1][j] 이다.
바로 이전의 숫자를 사용해서 만들 수 있는 i자리 수의 개수에서 현재의 숫자를 사용해서 만들 수 있는 i-1자리 수의 개수를 더하면 된다.
이게 왜 성립하냐면,
숫자 j-1이 마지막 자리에 오는 수에서 그 마지막 자리 수를 j로 바꾼 수들과
숫자 j가 마지막에 오는 i-1자리 수에서 마지막 바로 앞의 자리 수에 숫자 j를 추가한 수들의 합이기 때문이다.

예를 들어
dp[3][1] = 3 // 001, 011, 111
dp[2][2] = 3 // 02, 12, 22
이 둘을 사용해서 다음을 계산할 떄
dp[3][2]는 dp[3][1]의 마지막 "1"을 "2"로 바꾼 수 (002, 012, 112) 와 dp[2][2]의 마지막 수 바로 앞 자리에 "2"를 추가한 수 (022, 122, 222) 가 해당한다.

📌코드

package DP;

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

public class BOJ11057 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    // dp[i][j] = 수의 길이가 i일 때 숫자 j를 써서 나타낼 수 있는 수의 개수
    int[][] dp = new int[n+1][10];
    for(int i = 0; i < 10; i++){
      dp[1][i] = 1;
    }
    for(int i = 0; i < n+1; i++){
      dp[i][0] = 1;
    }
    for(int i = 2; i < n+1; i++){
      for(int j = 1; j < 10; j++){
        dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 10007;
      }
    }
    int answer = 0;
    for(int i : dp[n]){
      answer += i;
    }
    System.out.println(answer % 10007);
  }
}
``