[백준] 3985번 - 롤 케이크 [Java]

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

 

[백준] 3985번 - 롤 케이크 [Java]

[백준] 3985번 - 롤 케이크 [Java]

---

1.  아이디어

 

방청객이 받을 것으로 예상한 조각에 대한 카운팅 배열, 방청객이 실제로 받은 조각에 대한 카운팅 배열, 롤케이크 배열 3개를 활용해서 해결했다.

---

2. 문제풀이

 

정답의 최댓값을 구하기 위해 방청객이 받을 것으로 예상한 조각에 대한 카운팅 배열, 방청객이 실제로 받은 조각에 대한 카운팅 배열 두 개를 사용했다. 롤 케이크 배열은 방청객이 실제로 받은 조각에 대한 카운팅 배열을 만들기 위해 필요했다. 예상 조각은 입력에서 끝 값 - 시작 값 + 1로 바로 구할 수 있고 롤케이크 배열은 0이 아닐 때만 방청객의 번호를 넣으면 된다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int L = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        int[] before = new int[1 + N];
        int[] after = new int[1 + N];
        int[] cake = new int[1 + L];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            before[i] = end - start + 1;
            for (int j = start; j <= end; j++) {
                if (cake[j] == 0) {
                    cake[j] = i;
                    after[i]++;
                }
            }
        }

        int max1 = 0;
        int ans1 = 0;
        int max2 = 0;
        int ans2 = 0;
        for (int i = 1; i <= N; i++) {
            if (before[i] > max1) {
                max1 = before[i];
                ans1 = i;
            }
            if (after[i] > max2) {
                max2 = after[i];
                ans2 = i;
            }
        }

        System.out.println(ans1);
        System.out.println(ans2);
    }
}

---

4. 후기