백준 알고리즘 11057 오르막수

안녕하세요. 전상수 입니다.

DP 알고리즘중 쉬운 문제에 속하는 문제를 풀어보겠습니다.

왼쪽에서 오른쪽으로 오름차순으로 올라가는 수를 오르막수라고 합니다.

12345 이런식으로 되는 수를 얘기하는데 이 문제는 특이하게도 같은 수가 연속해도 오르막수라고 합니다.

2234 의 경우 2->2(같은수라 오르막) 2-> 3(수가 증가하여 오르막) 3 -> 4(수가 증가하여 오르막)

왼쪽에서 오른쪽으로 증가하면서 지나가서 오르막 수 입니다.

3676의 경우 367까지는 오르막 이지만 7 -> 6 으로 내려가면서 오르막 수가 되지 않습니다.

DP배열을 만들때는 현재 상태를 저장해야 하는데 현재 상태를 저장하는데 필요한 변수를 보면 아래와 같습니다.

1. 현재 상태의 인덱스 (11119 에서 현재 상태의 숫자가 9라면 5가 되겠죠)
2. 현재 상태의 숫자 (11119 에서는 1 또는 9가 되겠죠)

1번을 i, 2번을 v로 하겠습니다.

현재 상태를 dp[i][v]라고 할때 이전에 올수 있는 수는 dp[i - 1][v와 같거나 작은수] 가 됩니다.

이걸 식으로 나타내면 dp[i][v] = dp[i - 1][v] + dp[i - 1][v - 1] .... + dp[i - 1][0] 이 될수 있습니다.

이런식을 제귀적으로 풀면 될 것 같습니다.

코드를 보면 아래와 같습니다.