문제

문제 출처

문제 해결 전략

우선 일정한 규칙성을 찾아줘야한다.

0
1
2
3
4
5
6
7
8
9

10

20
21

30
31
32

40
41
42 - 18
43 19
44 20

50 21
51 22
52 23
53 24
54 25

.
.
.
.
210
321
310
320
이런 패턴만 봐도 앞자리 숫자는 전에 계산을 해뒀던 숫자들에 각각 자릿수가 하나씩 늘어나고 %10으로 나눈 나머지 숫자들만 뒤에 들어가게 된다.
그래서 동적 프로그래밍을 이용하여 앞서 기록을 해두었던 숫자들에 10을 곱하여 1의 자리 숫자만 inner-loop로 증가시켜서 기록하면 된다.

코드

#include <iostream>
#define N 1000001
using namespace std;

typedef long long ll;

ll num[N];

int main()
{
	int n;
	cin >> n;
	int ni = 10;
	for (int i = 0; i <= 9; i++)
		num[i] = i;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < (num[i] % 10); j++)
		{
			num[ni++] = num[i] * 10 + j;
		}
	}
	if (n > 1022)
		cout << "-1\n";
	else
		cout << num[n] << '\n';
}

내 힘으로 코드를 짜기 힘들었고 다른 사람들의 코드를 보고 비교해서 만들어보았다.. 골드 레벨 문제라 그래서가 아니라 아직 규칙성을 수식으로 표현하는데 익숙하진 않은 것 같다.!