[AC] 11057 오르막 수

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/11057.cpp

DP문제이다. 규칙을 찾는데 약 30분정도가 걸렸다. 좀 오래걸린거 같다. 

알고리즘은 다음과 같다.

1. 0~9까지 수별로 오르막수를 구해본다.

2. 자리수를 하나씩 높이면 그 직전수의 모든 합이 0번째 인덱스가 되고 그다음부터는 직전 녀석과 그 이전의 0번째부터 시작하는 배열값을 하나씩 매칭시켜 빼면 다시 수가 나오고 또 전체합을 통해 구한다.

3. 팁이라면 나는 0부터 차근차근 더해나갔는데 이러니까 10007 로 나눌때 상당히 까다롭다. 결국 난 해결하지 못했고 알고리즘을 수정했다. 수정한 알고리즘은 어차피 앞수가 9로시작하면 무조건 모든수가 999 이런식으로 진행되야 하므로 1개뿐이라는 사실을 알고 여기서 시작한다. 

여기서 시작하여 다시 똑같이 진행하면 9번째수에는 최종 합이 담기게 된다. 

이 문제는 알고리즘을 찾는것보다 이 나누는 경우를 어떻게 처리해야하나를 가지고 상당히 고민했던 문제이다.

결국 발상의 전환이었지만, 사람이란게 생각에 갖히기 시작하면 전환하기 참 힘든것 같다.