[PS] BOJ2109 순회공연 ( greedy ) wtih JAVA

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

2109번: 순회강연

 

◎ 문제풀이

 

위 문제는 d일 안에 강연을 해야함이 관건이다. 

 

 

5일 안에 강연을 해야함의 의미는 1~5일 사이에 강연을 해야한다는 의미이다. 그래서 처음에는 일수를 기준으로 일수마다 강연이 가능한 것 중에 최대값을 넣으려고 했다. 그랬더니 자료구조를 많이 생성해야하고 조건이 복잡해졌다. 일수가 아닌 강연을 기준으로 하면 문제가 풀린다.  강연을 하나씩 가져와서 스케줄을 최적의 스케줄로 하나씩 만들어 가면 되는 문제이다. ( Greedy 풀이 )

 

 

 

강연1을 가져온다.

강연1은 1일부터이고 1일은 스케줄이 비어있으니 스케줄을 잡는다.

 

강연2를 가져온다.

강연2는 5일부터이고 5일은 스케줄이 비어있으니 스케줄을 잡는다.

 

강연3을 가져온다.

강연3은 5일부터이고 5일은 강연2 스케줄이 잡혀있다. 

강연2와 강연3의 강연료를 비교한다. 

강연료2가 더 비싸므로 강연3은 전날로 이동한다. 

 

 

 

 

4일은 스케줄이 비어있으니 스케줄을 잡는다. 

이런 방식으로 강연을 하나씩 추가하고 하나씩 추가할때마다 최적의 스케줄을 만들어가면 된다. ( greedy )

 

greedy 발상이 어려운 문제였다. 

 

◎코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import static java.lang.Math.*;

//BOJ2109 순회공연
public class Main {
    static Course[] courses;
    static int maxDay = 0;

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        courses = new Course[n];

        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            maxDay = max(maxDay,d);
            courses[i] =  new Course(d,p);
        }
    }

    public static void solution(){
        int[] pays = new int[maxDay+1];

        for (Course course : courses) {
            for(int d=course.d;d>0;d--){
                if( course.p > pays[d] ) {
                    int tmpP = pays[d];
                    pays[d] = course.p;

                    int tmpD = d-1;
                    while(tmpD>0){
                        if(tmpP > pays[tmpD]){
                            int tmpP2 = pays[tmpD];
                            pays[tmpD] = tmpP;
                            tmpP = tmpP2;
                        }
                        tmpD--;
                    }
                    break;
                }
            }
        }

        int ans =0;
        for (int pay : pays) {
            ans += pay;
        }
        System.out.println(ans);
    }

    public static class Course {
        public int p;
        public int d;

        public Course(int d, int p) {
            this.p = p;
            this.d = d;
        }
    }
}