[BOJ] 1038. 감소하는 수

https://www.acmicpc.net/problem/1038 접근 방법 오랜만에 동적 프로그래밍 문제를 풀려니 어려웠었다.. 처음 접근 방법은 숫자들을 증가시키면서 이 숫자가 감소하는 숫자인지 확인해보았다. 당연히 이 방법은 시간초과가 났다... 그래서 구글링을 해서 찾아본 결과 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}의 각 부분 집합을 이용해 만들 수 있는 감소하는 수는 각각 1개이다. 예를 들어, {1, 4, 7, 9} 라는 부분 집합을 이용해서 만들 수 있는 감소하는 수는 9741 단 하나이다. 이것이 힌트이다. 그렇다면 이제 어떻게 하면 감소하는 수를 찾을 것 인가? 가 남았다. 먼저 0~9까지의 숫자를 받아서 [감소하는 수] + [감소하는 수의 맨 뒷자리의 수보다 작은 수] ..

2020.08.04