본문 바로가기

알고리즘

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

728x90

이 문제를 처음부터 탐색을 하면서 선택을 하던지 안 하던지를 정하는 문제이다 하지만 선택을 안 하는 경우는 딱 한가 지거나 없어야 한다는 것을 명심!!

 

간단하게 푸는 방법은 n개중 차례대로 하나씩을 빼면서 처음부터 탐색하는 것인데 그렇게하면 N^2이므로 시간 초과!

 

그래서 나는 하나를 선택하지 않은 경우와 전체를 선택한 경우 둘로 나눠서 문제를 풀어나갔다.

 

문제 풀이 

 

  1. 처음 것을 택한 경우와 택하지 않은 경우로 초기화
  2. 이전의 택한 경우의 합이 제한 상금보다 작거나 같을 경우 업데이트 --> 선택한 경우
  3. 이전의 택한 경우+현재 택하지 않은 경우 VS 이전의 택하지 않은 경우 + 현재 택한 경우 -->한번 참가 안 한 경우
  4. 이렇게 두 가지로 나눠서 두가지 경우 중에 답이 있으면  "Kkeo-eok" 없으면 "Zzz"

가장 처음 택한것돠 택하지 않은 것으로 초기화

 

 

두 번째 상황 -->

이 과정으로 지속적으로 끝까지 이어간다.

 

이러한 상황을 체크해주기 위해서

cal이라는 클래스를 선언했다 여기서 flag가 true면 이전의 값이 존재하는지를 나타내는 것이다.

 

그 후 차례대로 이 두 가지 경우를 비교해주면 된다.

 

이번 문제는 어렵다기보다 많은 생각을 요했던 문제이다. 어떻게 하면 쉽고 빠르게 비교를 할 수 있을지에 대한 문제이다.

 

전체 코드

 

더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class cal {
		long sum;
		boolean flag;

		public cal(long sum, boolean flag) {
			super();
			this.sum = sum;
			this.flag = flag;
		}
	}

	static int n;
	static cal plus, minus;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int min = Integer.parseInt(st.nextToken());
		int bonus = Integer.parseInt(st.nextToken());
		plus = new cal(bonus, true);
		minus = new cal(0, true);
		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			min = Integer.parseInt(st.nextToken());
			bonus = Integer.parseInt(st.nextToken());
			//
			if (minus.sum <= min && minus.flag) {
				minus.sum += bonus;
			} // 현재 저장되어있는 마이너스값 비교
			else {
				minus.flag = false;
			} // 하나 고르지 않았던 것

			if (plus.flag) {
				if (minus.flag) {
					minus.sum = Math.min(plus.sum, minus.sum);
				} 
				minus.flag = true;
			}
			if (plus.sum <= min && plus.flag) {
				plus.sum += bonus;
			} else {
				plus.flag = false;
			}

		}
		if (plus.flag || minus.flag) {
			System.out.println("Kkeo-eok");
		} else {
			System.out.println("Zzz");
		}

	}

}