1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.
www.acmicpc.net
큐를 이용한 솔루션을 생각하기 전에 한참 고민한 문제였다.
큐의 첫번째 원소의 일의 자리 수 보다 작은 숫자들을 뒤에 붙여서 다시 큐에 추가하는식으로 구현하였다.
|
#include <iostream>
#include <queue>
using namespace std;
queue<long long> q;
long long Solution(int N)
{
if (N == 0) return 0;
int lastNum, cnt = 0;
for (int i = 1; i < 10; i++)
q.push(i);
while (!q.empty())
{
int lastNum = q.front() % 10;
for (int i = 0; i < lastNum; i++)
q.push((q.front() * 10) + i);
cnt++;
if (cnt == N) return q.front();
q.pop();
}
return -1;
}
int main(void)
{
int N;
cin >> N;
cout << Solution(N) << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 20day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1074번: 게임 (0) | 2020.04.28 |
|---|---|
| 백준 7453번: 합이 0인 네 정수 (0) | 2020.04.26 |
| 백준 1051번 : 숫자 정사각형 (0) | 2020.04.24 |
| 백준 3085번: 사탕 게임 (c++) (0) | 2020.04.24 |
| 백준 2503번: 숫자 야구 (c++) (0) | 2020.04.23 |