[백준 19582] 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

CATEGORY : 그리디 (Greedy)

DIFFICULTY : GOLD IV

LANGUAGE : C++

LINK : BOJ 19582

Comment

2020 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2020) Div. 1 1번 문제의 매혹스러운 제목에 홀려 풀게 되었다. 무려 “200년간 폐관수련했더니 PS 최강자가 된 건에 대하여”..ㅋㅋ¹ 처음에 솔브했지만 찜찜하여 조금 더 생각해봤더니 TC가 부족해서 통과한 것이었다. 개인적으로 그리디 알고리즘은 테스트케이스와의 싸움인 것 같다.

1. 어떤 문제인가?

N개 대회 중 적어도 N-1개 대회에서 상금을 받을 수 있는지 여부에 대한 조사를 하는 문제이다. 각 대회는 X의 상금 제한이 있고 그 대회 우승 상금 P가 주어진다. 자세히

2. 접근 방식은?

1. 문제 조건인 시간 복잡도에 대한 분석. N 최대값은 10만. 한 개의 대회씩 제외시켜 가면서 모든 경우의 수를 구하면 O(N ² ) ²으로 시간 초과.

2. 상금 최댓값은 10억. 상금 총합의 최댓값은 10만 X 10억으로 정수범위를 넘어선다. long long 으로 선언해줄 것.

3. 테스트 케이스에 대한 분석

   • TC1

   

   두 번째 대회만 제외하면 나머지 ‘6-1’개의 대회에서 상금을 받을 수 있으므로 “Kkeo-eok”을 출력한다. 옆의 ‘Tolerance’는 최대 한 번 상금을 타지 못하는 것을 체크해준다. 음수가 되면 “Zzz” 출력.

   • TC2

   

   세 번째 대회의 최대 상금 제한 X에 걸린다. 여기에서 두 가지 경우로 생각할 수 있다. 위의 그림과 같이 세 번째 대회를 SKIP하는 경우. 이 테스트케이스에서는 SKIP해도 네 번째 대회에는 못나가므로 “Zzz” 를 출력한다.

   

   또는 위의 그림과 같이 ‘‘이전의 대회를 포기했더라면?’ 이라 생각하고 이전 대회의 상금을 빼준다. 이후 대회의 제한 조건을 최대한 통과시키기 위해서는 “이전 대회 상금 중 가장 큰 상금”을 제외해줘야겠다. Tolerance는 0이 된다. 하지만 다음 대회 상금 제한을 또 만족시키지 못하므로 “Zzz”를 출력한다.

3. 핵심 아이디어

위와 같이 접근을 하고 나면 O(N)으로 풀 수 있겠다는 생각이 든다.³ 모든 대회에 참가하면 상금 제한에 걸리지 않는 경우에 대한 처리는 쉽게 할 수 있으나 제한에 걸렸을 때에 대하여 조건 처리를 잘 해줘야 한다. 핵심 아이디어는 “n번째 대회에서 상금합을 최대한 작게 하자”이다.

변수 : 해당 대회의 상금 제한 X, 해당 대회 우승 상금 P, 이전 대회 최대 우승 상급 mxP, 수령한 상금 합 Sum

• Sum 이 X 제한보다 작을 때 : Sum에 상금 P를 더한다. mxP보다 P가 크면 갱신한다.
• 제한에 걸릴 때
  • 이전 대회(1번째~n-1번째 대회) 최대 상금 뱉고 통과하기 : mxP를 뱉어서 X 제한보다 작아지면 그렇게 한다. 단, 현재 대회(n번째 대회) 상금이 mxP보다 크면 mxP를 뱉지 않고 이번 대회를 포기해야 한다. 다음 대회(n+1번째 대회)를 출전하기 전의 sum값을 최대한 작게 해야한다고 생각해보자. mxP를 뱉는 것보다 P를 뱉어놓는 것이 더 그리디하다.^{*적합하다}
  • 이번 대회 뛰어넘기 : mxP를 뱉어도 X 제한에 걸린다면 이번 대회를 뛰어넘어야 한다.

4. 코드

#include<iostream>
using namespace std;
int N, X, P, mxP, tolerance = 1;
long long sum;	// 상금합 정수범위 넘음
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>N;
	for (int i = 0; i < N; i++) {
		cin >> X >> P;
		if (sum <= X) {	// 1. Sum 이 X 제한보다 작을 때
			sum += P;
			mxP = P > mxP ? P : mxP;
		}
		else if (sum - mxP > X || mxP < P) {	// 2. 제한에 걸릴 때 뛰어넘기
			tolerance--;
		}
		else {	// 3.제한에 걸릴 때 상금 뱉기
			tolerance--;
			sum -= mxP;
			sum += P;
		}
		if (tolerance < 0) {
			cout << "Zzz"; return 0;
		}
	}
	cout << "Kkeo-eok";
	return 0;
}

5. 틀왜맞?⁴

핵심 아이디어 중 “현재 대회(n번째 대회) 상금이 mxP보다 크면 mxP를 뱉지 않고 이번 대회를 포기해야 한다.” 는 조건 처리를 해주지 않았음에도 ‘맞았습니다!’를 받았다. 고민 결과 반례 TC를 만들 수 있었다. 다른 채점 코드들 중에서 sum 업데이트를 제대로 하지 않은 것도 통과가 되어서 그 부분에 대해서도 TC를 만들어 질문 게시판에 올려놓았다.

// 내 코드 에 대한 반례

6
1 3
4 5
9 5
8 100
13 2
15 3

출력 : Zzz
정답 : Kkeo-eok

//  sum 업데이트를 제대로 하지 않은 코드에 대한 반례

6
1 3
4 5
9 5
12 2
9 2
12 3

6. 그리디는? 다른 문제들..

아이디어를 내는 것과 검증하는 과정이 가장 중요한 것 같다.

solved.ac 의 그리디 문제들을 풀면서 그리디 최강자가 될 것.

Tweet Share