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

---

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

---

🔍 문제 풀이

풀이 방법

1. 가장 많은 조각을 기대한 사람 찾기 k - p + 1
2. 실제로 가장 많은 조각을 받은 사람 찾기
   • [방법1] cnt 변수 사용
   • [방법2] realCnt 배열 만들어 받은 조각 수 누적

💻 전체 코드

[방법1] cnt 변수 사용

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));

        int l = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        int[] cake = new int[l+1];


        int expectMax = -1;
        int expectNum = 0;

        int realMax = -1;
        int realNum = 0;
        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            // 기대값
            int val = k-p + 1;
            if(val > expectMax) {
                expectMax = val;
                expectNum = i;
            }

            // 실제 값
            int cnt = 0;
            for(int j=p; j<=k; j++) {
                if(cake[j] == 0){
                    cake[j] = i;
                    cnt ++;
                }
                if(cnt > realMax){
                    realMax = cnt;
                    realNum = i;
                }
            }
        }


        System.out.println(expectNum);
        System.out.println(realNum);
    }
}

[방법2] realCnt 배열 사용

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));

        int l = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        int[] cake = new int[l+1];
        int[] realCnt = new int[n + 1];


        int expectMax = -1;
        int expectNum = 0;

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            // 기대값
            int val = k-p + 1;
            if(val > expectMax) {
                expectMax = val;
                expectNum = i;
            }

            // 실제 값
            for(int j=p; j<=k; j++) {
                if(cake[j] == 0){
                    cake[j] = i;
                    realCnt[i]++;
                }
            }
        }

        // 실제 값 찾기
        int realMax = -1;
        int realNum = 0;

        for (int i = 1; i <= n; i++) {
            if (realCnt[i] > realMax) {
                realMax = realCnt[i];
                realNum = i;
            }
        }

        System.out.println(expectNum);
        System.out.println(realNum);
    }
}