백준 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);
}
}
📝 풀이
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[자릿수][시작값]으로 구성됩니다. 점화식을 구하기 위해 한 자릿수, 두 자릿수 정도 써보시면 점화식을 유추해낼 수 있습니다.
📜 후기
노트에 적으며 직접 점화식을 찾아보면 생각보다 쉽게 구할 수 있는 문제입니다.
Author And Source
이 문제에 관하여(백준 11057 오르막 수 (Java,자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jh5253/백준-11057-오르막-수-Java자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)