[자바] 백준 11108 - TV 전쟁 (java)

목차

문제 : boj11108

 

 

필요 알고리즘

• 동적 계획법 (DP), 그리디
  
  • 최선의 규칙을 모든 경우에 적용할 수 있는 그리디 문제이고, 직전까지의 최대 값을 알기 위해 DP를 사용했다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  이 문제에서 시간의 최대값은 10080이다. dp[x]를 '시간 x까지 획득 가능한 선호도의 최대치' 라고 정의해보자.

 

예를들어 예제 입력 1을 보자.

1
3
3 8 10
1 4 6
6 4 5

dp[0] 부터 dp[4] 까지는 어떤 tv 프로그램을 보더라도 아직 다 본게 아니므로 선호도 획득이 불가하므로 0이다. dp[5] 부터 dp[9] 까지는 시간1에 시작해 5에 끝나는 프로그램을 볼 수 있으므로 6이다. dp[10]부터 dp[10080]까지는 11이다. dp[11]에서 시간3에 시작해 시간11에 끝나는 선호도 10짜리 프로그램이 있긴하지만, 이미 11이 최대치이므로 버려진다.

 

  아무튼 dp[x]를 위처럼 정의하면 아주 간단해진다. 그냥 s+d가 작은 순서대로 확인하면서 dp[s+d] = max(dp[s+d-1], dp[s]+p) 를 계속해주면 된다. 말로 설명하자면 "x 시간에서의 선호도 최대값은 x-1 시간의 최대값 혹은 현재 살펴보고 있는 프로그램의 시작시간의 최대값(dp[s])에 현재 보고 있는 프로그램의 선호도(p)를 합친 값 중 최대값이다."

int[] dp = new int[MAX+1];
for (int i = 1; i <= MAX; i++) {
    dp[i] = dp[i-1];	// 우선 default값은 직전 최대값
    for (Tv cur : arr[i]) {	// s+d == i인 모든 프로그램에 대해
        dp[i] = Math.max(dp[i], dp[cur.s] + cur.p);	// dp[s]+p의 최대값을 찾는다.
    }
}

return dp[MAX];

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int MAX = 10080;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            sb.append(solve()).append('\n');
        }
        System.out.print(sb);
    }

    private int solve() throws Exception {
        int n = Integer.parseInt(br.readLine());
        List<Tv>[] arr = new List[MAX+1];
        for (int i = 0; i < arr.length; i++) arr[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            Tv tv = new Tv(s, d, p);
            arr[tv.e].add(tv);
        }

        int[] dp = new int[MAX+1];
        for (int i = 1; i <= MAX; i++) {
            dp[i] = dp[i-1];
            for (Tv cur : arr[i]) {
                dp[i] = Math.max(dp[i], dp[cur.s] + cur.p);
            }
        }

        return dp[MAX];
    }
}

class Tv {
    int s, e, p;

    public Tv(int s, int d, int p) {
        this.s = s;
        this.e = s + d;
        this.p = p;
    }
}