[백준 / #10844 / C++] 쉬운 계단 수

이 문제는 오랜만에 푼 실버 문제이다. 동적계획법 연습겸해서 풀어봤다.

 

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

10844번: 쉬운 계단 수

 

 

문제 해석:

 

 

이 문제는 계단 수의 갯수를 구하는 문제이다. 계단 수란 각각의 자리에서 인접한 수가 1씩만 차이가 나는 수를 말한다. 이 

 

말인 즉, 인접한 수는 +1 혹은 -1을 해야한다는 의미이다. 이런 과정을 거치려면 길이가 1인 계단 수에서 각각 +1, -1  한 수

 

를 뒤에 붙여주면 길이가 2인 계단 수가 완성되는데 앞에는 수 0이 오면 안되고 9에서는 +1이 불가능하므로 만약 0이 뒤에

 

붙으면 그 다음 길이의 계단 수에서 뒤에는 무조건 1이 붙을 수 밖에 없고 9 뒤에는 8 밖에 붙을 수 밖에 없다. 이 점을 참고

 

하면 문제를 쉽게 동적계획법(Dynamic programming, 이하 DP)로 풀어나갈 수 있다. 그 전의 길이의 계단수를 참고한다

 

는 점에서 DP를 떠올렸다.

 

 

 

알고리즘 해설 및 코드:

 

 

 

코드는 매우 간단하다. DP테이블을 뒤에 붙는 수로 잡으면 된다. 예를 들어 123이 온다면 맨 뒤에 붙은 수는 3이기 때문에

 

dp배열에서 [3]에 해당하는 수가 증가된다. 그렇다면 이런 dp 테이블을 어떻게 활용할까? 만약 현재 길이에서 끝에 2가 오

 

는 수를 구하고 싶다면 그 전 길이에서 끝이 1과 3이었던 수를 더해주면 2가 될 것이다. 왜냐하면 계단 수는 무조건 인접한

 

수가 +1 혹은 -1 이어야 하므로 이러한 결과가 도출된다. 그렇다면 이렇게 차례대로 길이별 뒤에 오는 수를 구해주고 내가

 

구하고자 하는 길이의 모든 수의 개수를 더해주면 답이 나온다. DP 테이블을 뒤에 오는 수로 활용할 생각만 했다면 쉽게

 

풀  수 있었을 것이다.