[백준알고리즘] 1019번: 책 페이지 -C++

[백준알고리즘] 1019번: 책 페이지 -C++

1019번: 책 페이지 (acmicpc.net)

1019번: 책 페이지

어렵다..... 결국 풀이를 봤다.... 풀이 보고도 이해를 겨우 했다....

다른 분들의 코드들도 모두 같길래, 아이디어를 가지고 비슷한 방식으로 이래저래 엄청 시도해봤는데 전혀 되는 게 없었다.. 다들 백준 님이 푸신 방법대로 풀었다.. 백준 님의 풀이는 링크의 강의자료를 보면 된다..

 

결국 나도 일반적으로 다들 푼 방법으로 코드를 올린다..

 

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

 

---

 

백준님의 풀이는 문제를 \(A\)에서 \(B\)까지 일반화해서 바라보고, 공통적으로 같이 카운팅 되는 영역을 체크했다. 그리고 공통으로 카운팅 되지 않는 부분의 처리는 \(A\)에서 증가하는 방향, \(B\)에서 감소하는 방향으로 체크해주었다.

 

여기서.. 공통적으로 카운팅 되는 영역을 나는 0부터 9까지로 일반화해서 찾았었다. 하지만, 공통으로 카운팅 되지 않는 영역에 대한 처리가 어려웠고 결국에는 풀이를 찾아보게 된 것이다.

 

백준 님과 다른 분들의 풀이도 마찬가지로 0부터 9까지 영역을 공통 카운팅 영역으로 잡는다. 따라서 \(A\)의 1의 자릿수가 0이 아니면 0으로 맞추기 위해 \(A\)를 증가시켰고, \(B\)의 1의 자릿수가 9가 아니면 9로 맞추기 위해 \(B\)를 감소시켰다.

그렇게 각각 \(A'\)과 \(B'\)으로 맞추었다면 공통으로 증가시키는 부분을 10의 거듭제곱과 \(B\)와 \(A\)의 차이를 통해 0부터 9까지의 수를 모두 일정하게 증가시켜주었다.

 

예제를 통해 예를 들어보겠다.

예제 입력은 \(A = 1, B = 11\)가 주어진 것과 같다. 여기서 \(A\)를 우선 1의 자릿수가 0이 되도록 하면, \(A = 10, B = 11\)가 된다. \(A\)를 증가시키면서 지나간 {1, 2, 3, 4, 5, 6, 7, 8, 9}는 각각 1씩 증가시켜준다.

이제 \(B\)를 1의 자리수가 9가 되도록 하는데, A와 같아지는 경우가 생기기 때문에 같아지는 부분에서 멈춰준다. 따라서 \(A=10, B=10\) 이 된다. 같아지는 부분에서 멈춰주는 이유는, \(A=10, B =9\) 가 된다면 {9, 10}에 대해서는 중복으로 처리하기 때문이다.

 

다른 분들이 큰 수에 대해서 예를 들어서 설명해주는 포스팅이 많은 것 같길래 예제를 통해서 간단히만 살펴보았다.

 

너무 어렵다 ;ㅅ; 왜 다른 방법이 안되는 것인지 모르겠다..

#include <iostream>
#include <vector>

void Solve(int end, std::vector<int64_t>& count);

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

	int n; // end
	std::cin >> n;
	std::vector<int64_t> count(10);

	Solve(n, count);

 	for (auto& c : count)
		std::cout << c << ' ';
}

// 범위 맞춰주는 영역(start의 1의 자리를 0으로, end의 1의 자리를 9로)의 값 처리
void subCounting(int num, std::vector<int64_t>& count, int tenPower)
{
	while (num)
	{
		count[num % 10] += tenPower;
		num /= 10;
	}
}

void Solve(int end, std::vector<int64_t>& count)
{
	int start = 1;
	int tenPower = 1;

	while (start <= end)
	{
		while (0 != start % 10 && start <= end)
		{
			subCounting(start, count, tenPower);
			start++;
		}

		if (end < start)
			return;

		while (9 != end % 10 && start <= end)
		{
			subCounting(end, count, tenPower);
			end--;
		}

		start /= 10; end /= 10;

		for (int i = 0; i < 10; i++)
			count[i] += (end - start + 1) * tenPower;
		tenPower *= 10;
	}
}