728x90
이 문제를 처음부터 탐색을 하면서 선택을 하던지 안 하던지를 정하는 문제이다 하지만 선택을 안 하는 경우는 딱 한가 지거나 없어야 한다는 것을 명심!!
간단하게 푸는 방법은 n개중 차례대로 하나씩을 빼면서 처음부터 탐색하는 것인데 그렇게하면 N^2이므로 시간 초과!
그래서 나는 하나를 선택하지 않은 경우와 전체를 선택한 경우 둘로 나눠서 문제를 풀어나갔다.
문제 풀이
- 처음 것을 택한 경우와 택하지 않은 경우로 초기화
- 이전의 택한 경우의 합이 제한 상금보다 작거나 같을 경우 업데이트 --> 선택한 경우
- 이전의 택한 경우+현재 택하지 않은 경우 VS 이전의 택하지 않은 경우 + 현재 택한 경우 -->한번 참가 안 한 경우
- 이렇게 두 가지로 나눠서 두가지 경우 중에 답이 있으면 "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");
}
}
}
'알고리즘' 카테고리의 다른 글
백준 3691 <컴퓨터 조립> (0) | 2020.10.24 |
---|---|
백준 1976 <여행가자> (0) | 2020.10.23 |
백준 20040 <사이클 게임> (0) | 2020.10.16 |
백준 19644 <좀비 떼가 기관총 진지에도 오다니> (1) | 2020.10.12 |
백준 20010 <악덕 영주 혜유> (0) | 2020.10.11 |