https://www.acmicpc.net/problem/27447
27447번: 주문은 토기입니까?
첫 번째 줄에는 손님의 수를 나타내는 정수 $N$과 토기에 담겨진 커피가 흙탕물이 되는 시간을 나타내는 정수 $M$이 공백을 사이에 두고 주어진다. ($1\le N,M\le 1\, 000\, 000$) 두 번째 줄에는 각 손님
www.acmicpc.net
풀이 방법
그리디 알고리즘 문제이다.
N크기의 배열 customers 을 생성하여 입력 받은 손님들의 도착 시간을 저장한다.
풀이를 위해 사용한 변수는 아래와 같다.
- togi: 현재 만들어져 있는 토기 개수
- coffee: 현재 토기에 담아 놓은 커피의 개수
- servingTarget: 현재 시점에서 가장 먼저 도착하는 손님 인덱스, 즉 서빙할 손님
- customer_idx: 배열에서의 손님 인덱스
시간 t=0 부터 증가시키면서 각 t초마다 일을 수행해주면 되는 데 아래 조건을 확인해주면서 각 조건에 맞게
최적의 일을 수행해준다.
- 손님이 도착한 시간에는 무조건 서빙해야 한다.
- t 와 serveingTarget의 도착 시간이 같은지 비교하여 같다면 서빙한다.
- 서빙할 때 coffee 가 0보다 크다면, 즉 커피가 토기에 담아져있다면 서빙한다.
- 그게 아니라면 즉시 서빙할 수 없으므로 fail
- 다음 손님을 위해 미리 커피를 준비해 놓을 수 있는지 확인한다.
- 손님이 s 시간에 도착한다고 하면 s에 서빙을 시작하여 서빙 완료 시간은 s+1
- 커피를 t시간에 담는다고 하면 t+1 에 커피 담기가 완료되며 이후 M초 안에는 서빙되어야 한다.
- 즉, s+1 <= t+M+1 이여야 하므로 s <= t+M 이면 t시간에 커피를 미리 담을 수 있다.
- 커피를 담아야 하는데 담을 토기가 없다면 토기를 만들어야 하므로 togi만 증가시킨다.
- 토기가 있다면 coffee 증가, togi 감소시키고 customer_idx 을 증가시켜 다음 손님을 본다.
- 위에 모두 해당되지 않는다면 할게 없으므로 토기나 만든다. togi 증가
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] customers = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
int t = Integer.parseInt(st.nextToken());
customers[i] = t;
}
int togi = 0; // 현재 만들어져 있는 토기 수
int coffee = 0; // 현재 토기에 담아놓은 커피 수
int servingTarget = 0; // 현재 시점에서 가장 먼저 도착하는 손님
int customer_idx = 0;
boolean success = true;
for(int t=0; t<customers[N-1]+1; t++) {
// 손님이 도착하면 서빙해야 함
if(customers[servingTarget] == t) {
if(coffee > 0) { // 커피가 담긴 토기가 있다면
servingTarget++;
coffee--;
} else {
success = false;
break;
}
// 지금 커피를 담아놓을 수 있으면 미리 커피 준비
} else if(customer_idx < N && customers[customer_idx] <= t+M) {
// 토기가 없으면 토기 만들기
if(togi == 0) {
togi++;
} else { // 토기가 있으면 커피 담기
coffee++;
togi--; // 토기 사용
customer_idx++;
}
} else {
togi++; // 뭐 없으면 토기 만들기
}
}
if(success) {
System.out.println("success");
} else {
System.out.println("fail");
}
}
}
'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 17822 원판 돌리기 자바(java) (1) | 2024.02.09 |
|---|---|
| 백준 13975 파일 합치기 3 자바(java) (0) | 2024.02.07 |
| 백준 11052 카드 구매하기 자바(java) (0) | 2024.01.31 |
| 백준 17609 회문 자바(java) (2) | 2024.01.31 |
| 백준 21315 카드 섞기 자바(java) (2) | 2024.01.30 |