문제
https://softeer.ai/practice/9496
문제 해석이 어려워서 그렇지 사실 간단하고 쉬운 풀이법이다. 우선 해당 문제의 노트가 닫힌 구간, 열린 구간에 대한 설명을 해주는데 어렸을 때 기억을 더듬어보면 중학생때 수학에 나오던 개념이다.
[a, b] = a 이상 b 이하
[a, b) = a 이상 b 미만
(a, b] = a 초과 b 이하
(a, b) = a 초과 b 미만
해당 관계성만 알게된다면, 사실 문제의 반은 접근했다고 볼 수 있다.
입력이 아래와 같다고 생각해보자
3
2 2 3
N = 3 이고, 각 각 자동차는 2, 3, 2의 작업 단계를 갖는다. 이를 순서대로 s1, s2, s3 라고 하고 공간 차지율을 확인해보면
s1(2) = [0, 1/2)
s2(2) = [0, 1/2)
s3(3) = [0, 1/3)
로 정리할 수 있다. 위의 상황일 때 시간 변화에 따른 작업 슬롯의 진행 과정을 보자
[0초]
s1이 [0, 1/2] 만큼의 공간을 차지하게 된다.
s2와 s3는 s1이 0 이상 1/2 미만의 공간을 차지하기 때문에 슬롯에 들어갈 자리가 없다.
작업을 종료한다.
[1초]
s1이 뒤로 밀려나가면서 [1/2, 1) 의 공간을 차지하게 된다. (1/2 이상 1 미만)
s2를 슬롯에 넣으려면 [0, 1/2) 공간(0 이상, 1/2 미만)을 차지해야한다.
s3를 슬롯에 넣으려면 [0, 1/3) 공간(0 이상, 1/3 미만)을 차지해야하고
따라서 s2 또는 s3 중 하나를 넣을 수 있는데 여기서 잘 생각해보면
s3를 먼저 넣게 된다면 s2가 2초 기다려야하고
s2를 먼저 넣게 된다면 s3는 1초만 기다리면 된다.
즉 공정 단계가 작을수록 먼저 넣는게 유리하다.
따라서 2초에는 s1이 [1/2, 1) 공간을 차지하고, s2가 [0, 1/2) 공간을 차지한다.
s3는 슬롯에 자리가 없기 때문에 대기한다.
[2초]
s1이 뒤로 밀려가면서 [1, 3/2)만큼의 공간을 차지하게 되는데 이때 슬롯 밖을 벗어나게 되면서 자동차 생산이 완료되었다. s2는 뒤로 밀려가면서 [1/2, 1)의 공간을 차지하게 되고 비로서 s3또한 슬롯에 위치할 수 있게 되므로 [0, 1/3) 공간을 차지한다.
[3초]
s2는 [1, 3/2)만큼의 공간을 차지하게 되는데 이때 범위가 슬롯 밖을 넘어서면서 자동차 생산이 완료되었다고 본다. s3는 뒤로 밀려가면서 [1/3, 2/3)의 공간을 차지한다.
[4초]
s3는 뒤로 밀려나면서 [2/3, 1) 만큼의 공간을 차지한다.
[5초]
s3는 뒤로 밀려나면서 [1, 4/3) 만큼의 공간을 차지하고 비로서 생산이 완료되었다.
위 과정을 보면 깨닫는게 있다.
1. 각 자동차들은 공정의 단계 만큼의 시간이 필요하다는 사실이다. 즉, s1과 s2의 공정 단계가 2이므로 생산되기까지 2초의 시간이 걸리고, s3는 단계가 3이므로 생산까지 3초가 걸린다. (만약 단계가 7인 자동차가 있다고 가정한다면 7초의 시간이 생산까지 걸린다.)
2. 공정 단계가 작을수록 먼저 들어간다.
3. 들어가는 순서를 오름차순으로 정렬 했을 때 (1, 2, 3, 4, ..., N) N번째 자동차는 N-1 초 후 들어간다.
위 단계에 의하면 가장 큰 단계가 생산까지 걸리는 초 + 가장 큰 단계가 작업 슬롯에 들어가는 초이다. 이를 소스코드로 나타내면 아래와 같다. (문제 이해가 까다로워서 그렇지 너무 허무...)
소스코드
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));
int N = Integer.parseInt(br.readLine());
int max = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) max = Math.max(max, Integer.parseInt(st.nextToken()));
System.out.println(max + N - 1);
}
}
댓글