[백준/C++] 의리 게임 (No. 28424)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 조건 쿼리에 맞게 빠르게 정답을 출력하도록 하면 되는 문제다.

 

단순히 구현으로 문제를 풀면 술을 먹는 로직에서 100,000*100,000 만큼의 연산으로 시간 초과가 될 수 있다.

 

이를 해결하기 위해 i번째 사람이 술을 마시고 난 다음 어떤 사람이 술을 마실 수 있는지 빠르게 찾도록 로직을 구현했다.

 

아래 그림을 예로 들어보자

 

fig1

 

그림과 같이 마실 수 있는 술의 양이 정해져 있다고 생각하면 1번 사람 이후에 2번과 3번 사람은 더 이상 술을 못 마시므로 바로 4번째 사람의 순서가 되게 된다.

 

그리고 마지막 사람의 다음 사람은 없으므로 -1을 이용해 뒤에 술을 마실 수 있는 사람이 없다는 것을 알려줬다.

 

 

그러므로 위 그림처럼 다음에 어떤 사람의 순서인지 계산한다면 이미 마실 수 있는 술의 양이 0이 된 사람은 더 이상 고려하지 않으므로 시간복잡도가 크게 줄어들게 된다는 사실을 알 수 있다.

 

그렇다면 다음에 어떤 사람의 순서인지 빠르게 계산하는 방법을 생각해보자

 

 i번째 사람의 다음 사람이 j라고 가정했을 경우 j가 마실 수 있는 술의 양이 0이 아니라면 j가 술을 마시면 된다.

하지만 j가 마실 수 있는 술의 양이 0이라면 더 이상 j는 술을 마실 수 없으므로 j의 다음 사람이 술을 마셔야한다.

 

이때, 다음에 술을 마셔야하는 사람 k를 찾았다면 i의 다음에 술을 마실 사람도 j가 아니라 k가 되도록 재귀적으로 갱신하면 된다.

(union-find 알고리즘에서 집합에 포함된 원소들의 대표 원소를 재귀적으로 갱신하는 방법을 떠올리면 된다) 

 

위 방법을 이용해 마신 술의 양을 저장해 두고 2번 쿼리가 올 때 마다 i번째 사람이 어느정도의 술을 마셨는지 판단하면 된다.

 

 

[아이디어 정리]

1. 각 사람이 술을 마시는 경우 마실 수 있는 술의 양이 0인 사람은 더 이상 술을 마시지 못하므로 이를 빠르게 계산하기 위해 i번째 사람의 다음에 어떤 사람이 술을 마시는지 빠르게 찾도록 배열을 이용해 구현한다.
2. 다음 사람을 갱신하는 방법은 다음 사람이 마실 수 있는 술의 양이 0인지 확인하고 재귀적으로 갱신한다.
3. 술 마신 양을 저장할 배열을 하나 만들어 2번 쿼리가 들어오면 배열에서 값을 찾아 출력한다.

 

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;


int FindNext(vector<int> &par, vector<long long>&V, int node)
{
	int nextNode = par[node];
	if (nextNode==-1)
	{
		return -1;
	}
	if (V[nextNode]==0)
	{
		return par[node] = FindNext(par, V, nextNode);
	}
	else {
		return nextNode;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, Q;
	cin >> N >> Q;
	vector<long long> V(N+1, 0);
	vector<long long> ans(N+1,0);
	vector<int> par(N + 1,0);
	for (int i=1; i<=N; i++)
	{
		cin >> V[i];
		par[i - 1] = i;
	}
	par[N] = -1;
	long long a, b, c;
	for (int i=0; i<Q; i++)
	{
		cin >> a;
		if (a==1)
		{
			cin >> b >> c;
			while (b != -1)
			{
				if (V[b]>c)
				{
					V[b] -= c;
					ans[b] += c;
					c = 0;
					break;
				}
				else
				{
					c -= V[b];
					ans[b] += V[b];
					V[b] = 0;
					b = FindNext(par, V, b);
				}
			}
		}
		else {
			cin >> b;
			cout << ans[b]<<"\n";
		}
	}
}

---

 

문제를 풀 때 잘못 이해해서 술을 버린다는게 아예 안마시고 버린다는 줄 알았다.

그래서 누적 합을 이용해 총 술의 양을 갱신하도록 구현을 해야하나? 생각했는데 다시 읽어보니 마시고 버리는거였다...

 

제대로 이해하고 나니 Union-Find 알고리즘과 비슷하게 재귀적으로 구현하면 빠르게 해결 할 수 있겠다는 생각이 들어서 바로 풀 수 있었던 문제였다

 

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