[백준] 1038 감소하는 수

✔️ 문제 링크

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

---

✔️ 문제 이해

1. 감소하는 수들은 아래와 같다. 

 

   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ... 20, 21 ... 30, 31, 32 ... 40, 41, 42, 43 .... 9,876,543,210]

 

2. n번째 감소하는 수를 구해야한다. 감소하는 수들이 담긴 배열을 만들어서 해결한다.

 

3. 감소하는 수중 최대값은 9,876,543,210이다. 약 98억이기 때문에 long long 자료형을 사용한다.

 

4. 큐를 이용해 감소하는 수들이 담긴 배열을 만든다.

 

---

✔️ 설계

1. 먼저 0~9까지 순서대로 큐에 넣는다.

 

Queue :  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

2. 큐에서 원소를 하나씩 꺼내서 감소하는 수들이 담긴 배열 arr 에 넣는다.

 

arr : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -> 숫자 0은 0번째 감소하는 수, 숫자 6는 6번째 감소하는 수..

 

3. 큐에서 원소를 하나씩 꺼낼때마다, 그 수로 이어지는 감소하는 수를 만들어 큐에 넣어준다.

 

4. ex) 큐에서 3을 꺼내면  3으로 시작하는 감소하는 수들을 (30, 31, 32) 만들어서 큐에 넣어준다. 

 

Queue :  [3, 4, 5, 6, 7, 8, 9, 30, 31, 32] -> 큐의 특성으로 새롭게 추가되는 감소하는 수들은 꼬리에 추가된다. 

---

✔️ 문제 회고

◾️ 이 문제는 DP로도 풀 수 있는데, DP에 익숙치 않아 완전탐색으로 접근했다.

◾️ 모든 숫자를 만들어 보려고 했는데, 시간 복잡도가 매우 커서 불가능했다.

◾️ 블로그 글을 통해 큐를 사용하여 푸는 방법을 알게됐고, 이를 적용하여 문제를 풀었다. 

◾️ 나올 수 있는 값중 최대값이 int 범위를 넘어섰다. 따라서 long long 자료형을 써야했다.

◾️ 나중에 DP로 풀어봐야겠다.

 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<queue>
using namespace std;

queue<long long> q;
long long arr[1000001]; //n의 최대값은 1000000이다, long long 자료형을 사용한다.

int main() {
	
	for (int i = 0; i <= 9; i++) //0~9까지 큐에 넣어준다.
		q.push(i);

	int idx = 0; //배열 순차접근을 위한 인덱스

	while (!q.empty()) { 
		long long num = q.front(); //큐에서 원소를 하나씩 꺼내서,
		arr[idx++] = num; //배열에 순차적으로 넣는다.
		if (idx > 1000000) break; //idx(n)이 1000000보다 크면 종료
		q.pop();

		//큐에서 꺼낸 수에서 이어지는 감소하는 수를 만들어 큐에 넣어준다.
		for (int i = 0; i < 10; i++) { 
			if (num % 10 > i) { //현재 1의 자리수보다 작은 수만 골라서,
				long long tmp = num * 10 + i; //감소하는 수를 만든다.
				q.push(tmp);
			}
		}
	}

	//감소하는 수는 1023번째부터는 존재하지 않는다. (1022번째 감소하는 수는 9,876,543,210 이다.)

	int n;
	cin >> n;
	if (n > 1022) 
		cout << -1;
	else
		cout << arr[n]; //n번째 감소하는 수를 출력한다.

	return 0;
}