(JAVA) 백준 11057번 : 오르막 수

 

https://www.acmicpc.net/problem/11057https://www.acmicpc.net/problem/11057

11057번: 오르막 수

 

 

DP(동적 프로그래밍) 문제이다.

 

 

길이 N에 해당하는 오르막 수를 구하는 문제인데,

 

오르막 수란

무조건 오름차순 인데, 중복된 숫자만 있어도 가능(인접한 수가 같아도 가능) 한 수

 

 

 

 

 

매커니즘

---

DP를 사용하기 위해서는 규칙을 찾아야 한다.

 

여기서는 2차원 int 배열을 적용시켰는데,

 

y는 길이 N을, x는 들어갈 수 있는 수(0 ~ 9)의 개수(=10) 을 나타낸다.

 

위 엑셀 캡쳐 화면을 보면

 

Y = 2일 때는 2자리를 뜻하므로 ㅁㅁ 에 해당하며,

X = 2인 경우에는 끝자리 수가 2에 해당하는 ㅁ2 에 해당한다.

 

끝자리 수 2를 얻기 위해서는 이전 숫자가 2보다 같거나 작아야 한다.

 

즉, ㅁ0, ㅁ1, ㅁ2

총 3가지를 얻을 수 있어서 dp[2][2] = 3이 된다.

 

 

또한,

 

점화식 DP[N][X] = DP[N - 1][0] + ... + DP[N - 1][X] 인데,

 

이를 줄이면

 

DP[N][X] = DP[N][X - 1] + DP[N - 1][X] 에 해당한다.

 

 

 

 

 

이렇게 나온 Y = N의 결과값들을 전부 더하면 끝!

** 참고로 문제에서 10007로 나눈 나머지를 출력하라 했으므로, 점화식 계산마다 나눠준다.

 

 

감사합니다.

 

소스코드

---