백준 23829: 인문예술탐사주간

지금까지 나는 아이디어가 필요하거나, 내가 모르는 것을 알게 되었거나 오랜 시간 막혔던 문제 위주로 글을 작성하였다.

그런데 이번 문제에서의 아이디어는 금방 떠올렸고, 딱히 모르는 것을 알게 된 문제는 아니다. 문제도 오늘 처음보고, 오늘 풀었다. 그래서 이 코드를 처음 짰을 때는 글을 적을 생각은 없었지만, 디버깅에 생각보다 오랜 시간이 걸렸고, 그 버그조차 너무 사소한 것이라서 반성을 목적으로 적어보려한다.

 

https://www.acmicpc.net/problem/23829

 

이 문제를 분석하며 떠올린 아이디어는 이분 탐색 + 누적 합이다. 나무의 위치들을 정렬해서, 입력으로 들어온 값을 이분 탐색으로 찾아서, 이 값으로 답을 계산하면 된다. 답은 어떻게 계산하나?

나무들의 위치를 차트로 나타낼 때 다음과 같다면

빨간색으로 표시된 영역이 이번에 구할 문제의 답이다. 즉,

 

답 = ((입력 값보다 작은 것들 갯수) * X - (입력 값 보다 작은 위치들의 합)) + ((입력 값 보다 큰 위치들의 합) - (입력 값보다 큰 것들의 갯수) * X))

 

다음과 같은 식을 구할 수 있다. 나는 처음에는 직접 이진탐색을 활용해서 답을 구하려했다.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
ll N, Q, P[100001], X;
ll A[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++)
	{
		cin >> P[i];
		A[i] = A[i - 1] + P[i];
	}
	sort(P, P + N + 1);
	while (Q--)
	{
		cin >> X;
		int l = 0, r = N + 1;
		while (l + 1 < r)
		{
			int m = (l + r) / 2;
			if (P[m] > X) r = m;
			else l = m;
		}
		ll ans = 0;
		if (l > 0) ans += (l * X) - A[l];
		if (r < N + 1) ans += ((A[N] - A[r - 1]) - (X * (N - r + 1)));
		cout << ans << '\n';
	}
}

하지만 틀리고 말았다. 나는 내 이진탐색 방식이 잘못된 줄 알고 c++의 lower_bound, upper_bound를 활용해서 답을 구하려 했다.

둘 다 이진탐색을 활용하는 메소드라서 sort된 배열에서 사용해야하는 것이 특징이다.

 

- lower_bound: 찾고자 하는 값보다 같거나 큰 숫자가 처음 등장하는 위치 반환

- upper_bound: 찾고자 하는 값을 초과하는 값이 가장 처음 나타나는 위치 반환

 

참조: https://velog.io/@chuu1019/c-lowerbound-upperbound-%ED%86%BA%EC%95%84%EB%B3%B4%EA%B8%B0

[c++] lower_bound, upper_bound 톺아보기

 

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
ll N, Q, P[100001], X;
ll A[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> Q;
	for (int i = 0; i < N; i++)
	{
		cin >> P[i];
		if (i == 0) A[i] = P[i];
		else A[i] = A[i - 1] + P[i];
	}
	sort(P, P + N);
	while (Q--)
	{
		cin >> X;
		
		ll ans = 0, lcnt = (lower_bound(P, P + N, X) - P), rcnt = N - (upper_bound(P, P + N, X) - P);
		if (lcnt > 0) ans += (lcnt * X) - A[lcnt - 1];
		if (rcnt > 0) ans += ((A[N - 1] - ((N - rcnt - 1 < 0) ? 0 : (A[N - rcnt - 1]))) - (X * rcnt));
		cout << ans << '\n';
	}
}

하지만 결국 이번에도 틀렸다. 무엇이 잘못되었을까? 이후 30분 가량 반례를 만들고, 답을 비교해보며 자신의 코드에 틀린점을 찾으려 노력했다. X가 나무의 위치와 똑같을 때, 모든 나무들의 위치보다 작거나 클 때, 나무들의 위치가 중복되었을 때 등등을 고려하였지만, 반례를 찾는데 실패했다.

 

문득 질문 게시판을 둘러보았을 때, 눈에 띄는 문장이 있었다.

 

나무 위치가 정렬되서 들어오지 않을 수도 있습니다.

 

이 문장을 보고 처음엔 "그래서 Sort했다"하며 넘어갔었다. 하지만 이 문장이 마음에 걸렸고, 다시 천천히 생각을 해본 결과 드디어 자신의 코드의 문제점을 발견했다. 정말 단순한 실수였는데, 내가 누적합을 구한 것은 Sort하기 이전 값이다. 그래서 답이 안나왔던 것이다. 그 동안 만든 반례는 쉽게 하기 위해 Sort된 값을 사용해서 문제점이 안 보였다. 정말 지금 생각해도 너무 어이없는 실수였다.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
ll N, Q, P[100001], X;
ll A[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++)
	{
		cin >> P[i];
	}
	sort(P, P + N + 1);
    for(int i = 1; i <= N; i++)
    {
        A[i] = A[i - 1] + P[i];
    }
	while (Q--)
	{
		cin >> X;
		int l = 0, r = N + 1;
		while (l + 1 < r)
		{
			int m = (l + r) / 2;
			if (P[m] > X) r = m;
			else l = m;
		}
		ll ans = 0;
		if (l > 0) ans += (l * X) - A[l];
		if (r < N + 1) ans += ((A[N] - A[r - 1]) - (X * (N - r + 1)));
		cout << ans << '\n';
	}
}

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
ll N, Q, P[100001], X;
ll A[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> Q;
	for (int i = 0; i < N; i++) cin >> P[i];
	sort(P, P + N);
	for (int i = 0; i < N; i++)
	{
		if (i == 0) A[i] = P[i];
		else A[i] = A[i - 1] + P[i];
	}
	while (Q--)
	{
		cin >> X;

		ll ans = 0, lcnt = (lower_bound(P, P + N, X) - P), rcnt = N - (upper_bound(P, P + N, X) - P);
		if (lcnt > 0) ans += (lcnt * X) - A[lcnt - 1];
		if (rcnt > 0) ans += ((A[N - 1] - ((N - rcnt - 1 < 0) ? 0 : (A[N - rcnt - 1]))) - (X * rcnt));
		cout << ans << '\n';
	}
}

결과적으로 두 코드 모두 통과되었다. 나는 누적합 문제를 풀때 입력과 함께 누적합을 구하는 버릇이 있는데, 이 버릇이 문제가 되었다. 앞으로는 입력값은 따로 두는 방향으로 고쳐보자.

생각보다 시간을 너무 소비했다..