[백준] No. 1038 - 감소하는 수 (C++)

문제

www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

풀이

 쉬운 듯 하지만 정답률이 낮은 이유는 감소하는 수의 최댓값은 9,876,543,210로 int형의 최댓값인  2,147,483,647보다 크기 때문에 int 형이 아닌 long형을 써주지 않아 그런것 같다.

 

본인의 경우에는 감소하는 수가 0~9까지만 이용가능 하므로, 11자리 이상 갈 일이 없다고 생각하질 않고 문제를 풀어 메모리 초과가 발생했다...

 

두 점만 명심하고 풀면 어렵진 않다.

 

 

FindDescendNumber(int cnt)를 재귀호출 하며 cnt로 현재 생성할 수의 자릿수를 넘겨준다.

 

vector<long long> descendNumberSet 에 생성한 감소 하는 수를 저장하여 중복되는 계산을 없애준다.

 

for문을 돌며 i의 값이 descendNumberSet의 가장 높은 자릿수보다 클경우에만 해당 값이 감소하는 값이다.

 

 

코드