[Java] 다이나믹 프로그래밍 (오르막 수)

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

11057번: 오르막 수

 

 

주말 하루종일 침대에만 있다가 죄책감이 들어 저녁 먹고 간단하게 홈트 후에 쉬운 문제를 풀어보았다.

다이나믹 프로그래밍은 예전에 문제를 많이 풀어봐서 바로 풀이법이 떠올랐다.

 

//    0   1   2  3  4
// 0      0   00          000
// 1      1   11,01       111,001,011
// 2      2   22,02,12    222,002,022,012,112,122
// 3      3   33,03,13,23 333,

사실 dp 규칙 찾는 거는 표로 그려보다 보면 금방 찾게 된다. 쉬우니까 미래의 나도 바로 알아챌 거라고 믿고 규칙설명은 패스

 

 

 

1. 1부터 N까지 행에 마지막 수가 0~9로 끝나는 10가지 열을 가지는 dp table 생성
2. dp [N][M]은 N자리 수를 가지고, 0부터 M까지의 숫자로 끝나는 모든 수의 합이다.

 

 

사실 최적화 하려면 할 수 있긴 한데 귀찮으니까 바로 제출했다.