BOJ 1781 (시간초과..)

2020-08-16

백준

위 문제는 백준 사이트의 알고리즘 1781 문제에 관한 설명입니다.

BOJ 1781

컵라면

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다.

하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호 1 2 3 4 5 6 7
데드라인 1 1 3 3 2 2 6
컵라면 수/ 6 7 2 1 4 5 1

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N 이하이다.

또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 32비트 정수형 범위 이내이다.

입력

첫 줄에 숙제의 개수 N (1<=N<=200,000)이 들어온다.

다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;



class Main {
	static class MyComparator implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			// TODO Auto-generated method stub
			if (o1[0] == o2[0])
				return o2[1] - o1[1];
			return o1[0] - o2[0];
		}

	}
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] array = new int[N+1][2];
		boolean[]visited = new boolean[N+1];
		for (int i = 1; i <= N; i++) {
			StringTokenizer st =new StringTokenizer(br.readLine());
			int deadLine = Integer.parseInt(st.nextToken());
			array[i][0] = deadLine;
			int cupRamyeon = Integer.parseInt(st.nextToken());
			array[i][1] = cupRamyeon;
		}
		Arrays.sort(array, new MyComparator());
		int sum = 0;
		for(int time = 1 ; time <= N;time++)
		{
			for(int i = 1; i <= N; i++)
			{
				if(array[i][0] <= time && !visited[array[i][0]])
				{	
					sum+= array[i][1];
					visited[array[i][0]] = true;
				}
				else {
					continue;
				}
			}
		}
		System.out.println(sum);
	}
}

결과부터 말하자면

시간초과 났습니다..

처음엔 Comparator를 연습하려고 푼 문제였는데 배열로 풀었더니 시간 초과가 났습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Ramyeon> priorityQueue = new PriorityQueue<Ramyeon>();
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int deadLine = Integer.parseInt(st.nextToken());
			int cupRamyeon = Integer.parseInt(st.nextToken());
			priorityQueue.offer(new Ramyeon(deadLine, cupRamyeon));
		}

		int sum = 0;
		int time =1;
		Ramyeon temp1;
		while (!priorityQueue.isEmpty()) {
			Ramyeon temp = priorityQueue.poll();
			if (time <= temp.deadLine) { 
				System.out.println(temp.deadLine + " " + temp.Ramyeon);
				sum += temp.Ramyeon;
			}
			while (!priorityQueue.isEmpty() && priorityQueue.peek().deadLine == time) {
				temp1 = priorityQueue.poll();
				System.out.println("poll : " + temp1.deadLine + " " + temp1.Ramyeon);
			}
			time++;	
		}
		System.out.println(sum);
	}
}

class Ramyeon implements Comparable<Ramyeon> {
	int deadLine;
	int Ramyeon;

	Ramyeon(int deadLine, int Ramyeon) {
		this.deadLine = deadLine;
		this.Ramyeon = Ramyeon;
	}

	@Override
	public int compareTo(Ramyeon o) {
		// TODO Auto-generated method stub
		if (this.deadLine == o.deadLine)
			return o.Ramyeon - this.Ramyeon;
		return this.deadLine - o.deadLine;
	}
}

우선순위 큐로 Comparable도 활용해서 수정 중 입니다..

반례도 나오는걸 찾았습니다..

테스트 케이스 대다수는 통과하지만 몇개 통과하지 않아서 금방 고칠줄 알았는데..

몇 시간 째 잡고 있지만 해결이 안되었습니다.

혹시 해결하는 방법을 알아내신분이 계신다면 댓글 남겨주세요!

« BOJ 2529 BOJ 1987 »