백준 1038 감소하는 수 [c++]
in Develop / Solving
c++
최근에 문제푸는 걸 드문드문 올리고 있다. 그냥 뭔가 올리고 싶은 문제가 별로 없다. 이번 문제는 재미있었어서 글을 남긴다.
문제 분석
- 음이 아닌 정수 X가, 첫번째 자리부터 끝자리까지 수가 감소하는 수를 ‘감소하는 수’라고 함.
- 321, 950등은 감소하는 수이고, 322, 958은 감소하는 수가 아니다.
- 0이 0번째 감소하는 수, 1이 1번째 감소하는 수 이렇게 올라갈 때,
- n이 주어지면 n번째 감소하는 수를 구하여라.
- n번째 감소하는 수가 없으면 -1을 출력해라.
입력조건
숫자 n
풀이과정
- 시간초과의 핵심은 ‘n번째 감소하는 수가 없으면’이라는 조건이다.
- n은 1000000까지 올라가는 데, 실제로 n > 1022면 -1을 출력해야 한다.
- 따라서, n이 1000000을 받았다고 해서 이를 반복을 다 돌려버리면 시간초과가 난다. 이를 적절히 커트해야 한다.
단순하게 n > 1022일 때 -1을 출력하고 끝내버려도 되지만, 그보다는 더 평이하게 코드를 작성하고 싶었고, 최대 숫자를 계산한 뒤 더 계산할 수 없으면 -1을 출력하도록 하였다.
- 기본적으로 계산을 숫자 배열을 이용하였다.
- 최대 감소하는 수는 9876543210으로 10자리의 수이고, 이를 10개의 숫자배열을 이용해서 한 자리에 한 숫자가 들어가는 배열을 만든다.
- 0부터 출발하여, 1의 자리를 하나씩 올리면서 계산한다.
- 이 때, 앞자리보다 뒷자리가 커지는 경우가 발생하면 바로 뒷자리들을 전부 0으로 만들어버리고, 앞자리를 하나 올린다.
당연히 더하다가 10을 넘어가는 경우도 처리한다.
- 결론적으로 그냥 1부터 계산하는 백트래킹이랑 다를 건 없지만,
- 숫자 배열을 이용하고 재귀를 이용하지 않았다는 점에서 조금 독특하게 풀었다고 생각하여 풀이를 남긴다!!
전체 코드
#include <iostream>
/*
n번 자리가 x면, n+1번 자리는 n-1까지의 숫자가 올 수 있고, 이는 총 n개의 경우가 됨.
찾아야 되는 위치를 받아 오기.
9 876 543 210 < 최대 수 98억
n = 1022일 때 최대
*/
int main() {
int n;
std::cin >> n;
int count = 0;
int target[10] = {12, 12, 12, 12, 12, 12, 12, 12, 12, 0};
while(count < n) {
target[9]++;
outer : for(int i = 9; i >= 1; i--) {
// 자리를 넘겨야 하는 상황.
if((target[i] != 12 && target[i-1] <= target[i] )|| target[i] == 10) {
// 수 더하기,
target[i-1] += 1;
int f = i-1;
while(target[f] == 10) {
if(f == 0) {
std::cout << -1;
return 0;
}
target[f--] = 0;
target[f] += 1;
}
if(target[f] == 13) target[f] = 1;
// 뒤에를 전부 0으로 초기화.
for(int j = i; j <= 9; j++) target[j] = 0;
// 다음 반복 실행.
goto outer;
}
}
// 여기에 오면 다 통과된 것.
count++;
// 디버그
// for(int num : target)
// std::cout << num << " ";
// std::cout << std::endl;
}
// 정답 출력.
// std::cout << "\nans ";
for(int num : target) if(num != 12) std::cout << num;
}
