백준 1781 : 컵라면 (Java)

 

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

1781번: 컵라면

 

 

오늘도 알고리즘!

 

그리디 알고리즘은 풀면 풀수록 사고력에 도움이 된다는 점!

 

그리디 알고리즘의 상위문제 컵라면 입니다.

 

먹을 수 있는 최대의 컵라면을 먹어야 하기 때문에!

 

컵라면을 기준으로 먼저 정렬을 합니다.

 

그 시간 대에 먹을 수 있는 컵라면의 수가 같다면?!

 

데드라인을 기준으로 정렬해 줍니다 (사실 큰 차이는 없어요, 이유는 밑에!)

 

Comparable을 사용하여 정렬을 해줍니다.

 

이후 N+1만큼의 boolean 배열을 하나 선언해서

 

데드라인에 먹을수 있는 최대의 라면을 담아줍니다.

 

만약 그 데드라인에 먹을 수 있었던 라면이 있다면

 

이전 데드라인에 먹어줍니다.

 

 

이렇게 하면 풀 수 있습니다

 

사고력이 요구되는 문제가 아니였나 생각됩니다.

 

그리디 문제 답게 사고해야하는 방식, 접근해야하는 방식이 조금 까다로웠던 문제입니다.

 

하지만 시뮬레이션과 그리디 문제는 풀면 풀수록 좋다는 점!

 

더 나은 프로그래밍을 위해 한번 풀어보시는걸 추천합니다.

 

 

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

public class Main {
	static class Ramen implements Comparable<Ramen> {
		int n, d, c;

		public Ramen(int n, int d, int c) {

			this.n = n;
			this.d = d;
			this.c = c;
		}

		@Override
		public int compareTo(Ramen o) {
			if (o.c == this.c)
				return this.d - o.d;
			return o.c - this.c;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		Ramen[] r = new Ramen[N];
		boolean b[] = new boolean[N + 1];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			r[i] = new Ramen(i + 1, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		Arrays.sort(r);
		int ans = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = r[i-1].d, index = i-1; j > 0; j--) {
				if(!b[j]) {
					ans += r[index].c;
					b[j] = true;
					break;
				}
			}
		}
		System.out.println(ans);
	}
}