[백준알고리즘] 1038번: 감소하는 수 -C++

[백준알고리즘] 1038번: 감소하는 수 -C++

1038번: 감소하는 수 (acmicpc.net)

1038번: 감소하는 수

쉬운 듯 안 쉬운 듯한 문제..

 

DFS로 푸시는 분들이 많으신 것 같고 풀이가 많으신 것 같지만, 나는 DP로 풀었다. DP로 푸는 방법 중에서도 벡터를 두개만 사용해서 문제를 풀었다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

처음 문제를 접했을 때에는 숫자를 1씩 증가시키면서.. 그러면서 각각의 수가 감소하는 수인지 확인하는 방법으로 코드를 작성했다. 코드를 작성하고 있을 때도 당연히 시간초과가 날 것이라고 생각했고, 실제로도 시간 초과 때문에 테스트하는 과정에서 N이 100, 1000 이런 경우에도 정신을 못 차리는 것을 봤다.

 

그래서 다시 뜯어 고치는데, 이런 경우에는 규칙이 있어 어떠한 점화식에 의해 딱! 답이 나올 것이라고 생각했다.

 

그러고 차례대로 감소하는 수를 적어보았고, 거기서 규칙을 찾게 되었다.

 

우선, 10 보다 작은 수들에서 감소하는 수는 다음과 같다. 첫 번째 행은 시작하는 수(가장 큰 자릿수의 숫자)다.

0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9

 

그다음, 10 보다 크거나 같고 100 보다 작은 수들에서 감소하는 수는 다음과 같다.

0	1	2	3	4	5	6	7	8	9
	10	20 21	30 31 32	40 41 42 43	50 51 52 53 54	60 61 62 63 64 65	70 71 72 73 74 75 76	80 81 82 83 84 85 86 87	90 91 92 93 94 95 96 97 98

이쯤되면 특징을 찾을 수 있는데 그래도 한번 더 살펴보도록 하겠다.

 

100보다 크거나 같고 1000 보다 작은 수들에서 감소하는 수에서 살펴보겠다.

0	1	2	3	4	5	6	7	8	9
		210	310 320 321	410 420 421 430 431 432	510 520 521 530 531 532 540 541 542 543	..	..	..	..

 

너무 많아서 생략하겠다... 그래도 이정도면 특징을 알 수 있다.

 

두 자리의 숫자를 다룰 때는 한 자리의 숫자에 의해 생성되고, 세 자리의 숫자를 다룰 때에는 두 자리의 숫자에 의해 생성된다.

아까 표에서 했던 것을 다루면 다음과 같이 보면 된다.

한 자리 숫자와 두 자리 숫자와의 관계

역시 마우스로 끄적이는건 퀄리티가 떨어지지만.. 그래도 두 자리 숫자 중 시작하는 숫자(십의 자리 숫자)가 \(X\)일 때, 뒤이어 나오는 수는 한 자리 숫자 중 \(0\)으로 시작하는 숫자부터 \(X-1\)으로 시작하는 숫자까지가 뒤이어 붙는다.

음.. 말로 설명하니까 좀 뭐라하는지 모르겠는데..

십의 자리 숫자가 3으로 시작하면, 일의 자리 숫자는 한 자리 숫자 중 0~2로 시작하는 수가 뒤이어 나온다.

 

여기서 와닿지 않는다면, 다음 경우를 보면 된다.

두 자리 숫자와 세 자리 숫자와의 관계

이 경우를 보면 더 와닿을 수 있다.

 

세 자리 숫자에서 백의 자리 수가 2로 시작하는 경우 십의 자리의 숫자가 0으로 시작, 1로 시작하는 경우가 뒤이어 붙을 수 있다. 해당하는 경우는 \(\{10\}\)이 전부이기 때문에 \(\{210\}\)이 가능하다.

 

세 자리 숫자에서 백의 자리 수가 3으로 시작하는 경우 십의 자리 숫자가 0으로 시작, 1로 시작, 2로 시작하는 경우가 뒤이어 붙을 수 있다. 해당하는 경우는 \(\{10, 20, 21\}\)이다. 따라서 백의 자리 수가 3으로 시작하는 경우는 \(\{310, 320, 321\}\)이다.

 

그래서 이러한 규칙을 적용했다.

 

---

 

그래서 두 개의 벡터만을 이용해서 문제를 풀었다. 자릿수가 홀수인 경우와 짝수인 경우만 존재하면 된다. 각 자릿수에서 가능한 숫자는 앞 자릿수의 경우만 생각해주면 되기 때문이다.

 

그렇게 가능한 수를 확인해나가면서 n번째 감소하는 수가 맞는지 확인해주었다.

 

여기서 처음에 인지를 하지 못했던 부분이 long long type을 이용해야 한다는 것이다. 생각없이 코딩했나; 최대로 큰 수가 9876543210이 되기 때문에 long long type을 해주어야 하며, string을 통해 자리수 등을 처리했기 때문에 숫자로 바꿔주기 위해서는 stoll을 사용해주어야 했다.

 

또한, 감소하는 수가 9876543210보다 커지는 경우는 없기 때문에 그러한 경우에는 주어진 n을 절대 만족하지 못하기 때문에 -1을 return 해야 한다.

 

아래는 C++ 코드다. 이해가 쉬울 것이라고 생각한다..

#include <iostream>
#include <vector>
#include <string>

int64_t solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cout << solve();
}

int64_t solve(void)
{
	int n;
	std::cin >> n;

	if (n < 0)
		return -1;

	if (n <= 10)
		return n;

	int count = 9;
	std::vector<std::vector<std::string>> oddVector(10);
	std::vector<std::vector<std::string>> evenVector(10);

	for (int i = 0; i < 10; i++)
		oddVector[i].push_back(std::to_string(i));
	
	int len = 2;
	while (len <= 10) // 9876543210
	{
		std::vector<std::vector<std::string>>& target = (len % 2 ? oddVector : evenVector);
		std::vector<std::vector<std::string>>& opponent = (len % 2 ? evenVector : oddVector);

		for (auto& t : target)
			t.clear();

		for (int i = 0; i < 10; i++)
			for (int j = 0; j < i; j++)
				for (auto oppo : opponent[j])
				{
					target[i].push_back(std::to_string(i) + oppo);
					count++;

					if (count == n)
						return std::stoll(target[i].back()); // string to long long
				}

		len++;
	}

	return -1;
}