알고리즘 공부/백준
[백준] No. 1038 - 감소하는 수 (C++)
EVEerNew
2020. 10. 24. 23:23
반응형
문제
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를
www.acmicpc.net
풀이
쉬운 듯 하지만 정답률이 낮은 이유는 감소하는 수의 최댓값은 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의 가장 높은 자릿수보다 클경우에만 해당 값이 감소하는 값이다.
코드
반응형