[BOJ][1038] 감소하는수
1401 단어 CodingTestCodingTest
문제
문제 해결 전략
우선 일정한 규칙성을 찾아줘야한다.
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';
}
내 힘으로 코드를 짜기 힘들었고 다른 사람들의 코드를 보고 비교해서 만들어보았다.. 골드 레벨 문제라 그래서가 아니라 아직 규칙성을 수식으로 표현하는데 익숙하진 않은 것 같다.!
Author And Source
이 문제에 관하여([BOJ][1038] 감소하는수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@easttwave/BOJ1038-감소하는수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)