[Algorithm/Java] 백준 3985번 - 롤 케이크
https://www.acmicpc.net/problem/3985
🔍 문제 풀이
풀이 방법
- 가장 많은 조각을 기대한 사람 찾기
k - p + 1
- 실제로 가장 많은 조각을 받은 사람 찾기
- [방법1]
cnt
변수 사용 - [방법2]
realCnt
배열 만들어 받은 조각 수 누적
- [방법1]
💻 전체 코드
[방법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);
}
}
댓글남기기