[백준 30621] 어? 금지 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/30621

30621번: 어? 금지

 

 

문제

'어?'

팀 대회 중 주변에서 '어?'라는 말이 들리면 마음이 혼란해진다. 그렇다고 해서 '어?'를 남발하면 혼란보다는 짜증이 앞서게 된다. 이를 잘 알고 있는 성우는 적당한 선을 지키면서 대회장에 최대한 큰 혼란을 주려고 한다.

• 대회는 시각 0에 시작한다.
• 성우가 '어?'를 외칠 수 있는 시각은 N개가 있고, i 번째 시각은 ti다. (1 ≤ i ≤ N)
• 만약 성우가 시각 ti에 '어?'를 외치려 한다면, 성우는 시각 (ti - bi) 부터 지금까지 '어?'를 외친 적이 없어야 한다.
  • 성우가 정확히 시각 (ti - bi)에 '어?'를 외쳤더라도 시각 ti에 '어?'를 외칠 수 없다.

성우가 시각 ti 에 '어?'를 외치면 대회장에 ci 만큼의 혼란이 가해진다. 최종 혼란은 대회장에 가해진 혼란의 합이다.

성우는 대회장에 줄 수 있는 최종 혼란의 최댓값이 궁금해졌다. 성우를 위해 이를 구해주자.

 

입력

첫 번째 줄에 성우가 '어?'를 외칠 수 있는 시각의 개수 N이 주어진다. (1 ≤ N ≤ 100000)

두 번째 줄에 정수 t1, t2, ..., tN이 공백을 사이에 두고 주어진다. (1 ≤ ti ≤ 10^9 ; ti-1 < ti) 

세 번째 줄에 정수 b1, b2, ..., bN이 공백을 사이에 두고 주어진다. (1 ≤ bi ≤ 10^9 ; bi < ti) 

네 번째 줄에 정수 c1, c2, ..., cN이 공백을 사이에 두고 주어진다. (1 ≤ ci ≤ 10^9) 

 

출력

첫 번째 줄에 성우가 대회장에 줄 수 있는 최종 혼란의 최댓값을 출력한다.

풀이

접근법

1. N이 100,000 이고, ti가 10^9까지 있으니까 dp를 사용한다.
2. ti - bi 시에 어? 를 외쳤는지 찾기 위해 완탐보다는 이진탐색으로 인덱스를 구해야겠다.
3. 근데 ti == bi이면 0시부터 외치면 안되는거니까 ci가 최대겠다.
4. 현재 외치지 않는다는 것은, 이전 시각에 외치던 외치지 않던 그 최댓값이겠다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        int[] t = new int[N];
        int[] b = new int[N];
        int[] c = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) t[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) b[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) c[i] = Integer.parseInt(st.nextToken());
        
        // 1. N이 100,000 이고, ti가 10^9까지 있으니까 dp를 사용한다.
        // ci가 10^9 까지이고, 그 합이니까 long으로 지정한다.
        long[][] dp = new long[N][2];
        dp[0][0] = c[0];
        for(int i=1;i<N;i++) {
            // 3. 근데 ti == bi이면 0시부터 외치면 안되는거니까 ci가 최대겠다.
            if (t[i] == b[i]) dp[i][0] = c[i];
            else {
                int idx = binary(t[i]-b[i], t, N);
                if (idx == -1) dp[i][0] = c[i];
                else dp[i][0] = Math.max(dp[idx][0], dp[idx][1]) + c[i];
            }
            // 4. 현재 외치지 않는다는 것은, 이전 시각에 외치던 외치지 않던 그 최댓값이겠다.
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);
        }
        System.out.println(Math.max(dp[N-1][0], dp[N-1][1]));

    }
    
    // 2. ti - bi 시에 어? 를 외쳤는지 찾기 위해 완탐보다는 이진탐색으로 인덱스를 구해야겠다.
    private static int binary(int num, int[] t, int N) {
        int s = 0;
        int e = N-1;
        while(s <= e) {
            int mid = (s+e) / 2;
            if (t[mid] == num) return mid-1;
            else if (t[mid] < num) s = mid + 1;
            else e = mid -1;
        }
        return e;
    }
}

 

 

약 20분 걸렸다.