백준 1038 감소하는 수

문제링크 : https://www.acmicpc.net/problem/1038

아이디어

• N번째까지 순회하면서 숫자를 확인
• 순회할때 조건
  • 1자리수는 통과
  • 자리수 올라갈떄, 10 곱한뒤에, 가장 마지막 수보다 작은것들만 추가
  • 그럼 이전에 감소한 수를 재사용해야함 > 큐를 사용해서 이전에 계산한 값 넣어주기
• 일의 자리 일때 조심!

시간복잡도 계산

• N까지 순회 : O(N)
• 마지막 일의자리 10개 순회 : O(10)

자료구조

• queue <long long>
  • 최대 숫자 될수 있는수 10자리 > long long 사용
  • 감소하는 수이기 때문에 숫자가 총 10개

코드(C++)

#include <iostream>
#include <queue>
 
using namespace std;
typedef long long ll;
 
int main() {
    int N; cin >> N;
    
    // 1의 자리 미리 출력
    // 큐에 넣은 후 출력하려고하면 복잡해짐
    if(N <=9) {
        cout << N << '\n';
        return 0;
    }
    
    queue<ll> q;
    for(int i=0; i<=9; i++) q.push(i);
    
    int cnt=9;
    
    while(!q.empty()) {
        ll eq = q.front(); q.pop();
        
        // 일의자리 구해서 작은수까지 순회
        int lastNum = eq%10;
        for(int i=0; i<lastNum; i++) {
            
            ll ev = eq*10 + i;
            q.push(ev);
            cnt++;
            if(cnt==N) {
                cout << ev << '\n';
                return 0;
            }
        }
    }
    
    cout << -1 << '\n';
    
    return 0;
}
 

문제유형

• 브루트포스 - 큐
  • 특정 순번의 값을 확인해야할때
  • 이전에 사용한 값을 재활용 할수 있을 때
  • 큐에 넣고, 뽑으면서 다음 값을 구함