문제 풀이
그리디
start = 연속된 일정의 시작날짜
end = 연속된 일정의 종료날짜
max = 연속된 일정 중 일정이 가장 많은 날의 일정 갯수
answer = 필요한 코팅지의 총면적
cal[i] = i일의 일정 갯수
전체 일정의 시작날짜부터 종료날짜까지 cal값을 1씩 증가시켜 해당 날짜에 일정이 있음을 나타냄
그 후 1일부터 365일까지 cal 값을 확인해 0이면 end에 i - 1 대입 후 코팅지 면적 계산 후 answer에 추가하고 max에 0, start에 i + 1 대입
0이 아니면 max와 비교해 최댓값 max에 대입
answer 출력하면 정답
풀이 설명
연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기로 코팅지를 자른다는 것은 일정 하나의 세로의 길이가 1이고, 하루의 폭이 1이라고 했으므로 가로의 길이가 연속된 일정의 날짜 수가 되고, 세로의 길이가 연속된 날들 중 일정이 가장 많은 날의 일정 수로 직사각형을 만드는 것이 된다.
따라서 연속된 날짜의 일정의 날짜 수와 연속된 일정의 날들 중 일정의 최대 개수를 구하기 위해 각 날짜의 일정의 갯수를 구하면 날짜를 1일부터 365일까지 순서대로 확인하며 일정 갯수가 0이 아니게 된 날짜부터 일정 갯수가 0이 되게 되는 전날까지 일정이 연속되어 있는 것이고, 그 날짜동안 확인한 일정 갯수의 최댓값이 일정이 가장 많은 날의 일정 수가 되므로 이를 곱하면 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기를 구할 수 있다.
따라서 cal[i]를 i일의 일정 갯수로 정의하고, start를 연속된 일정의 시작날짜, end를 연속된 일정의 종료날짜, max를 연속된 일정 중 일정이 가장 많은 날의 일정 갯수, answer를 필요한 코팅지의 총면적라고 정의하고 1일부터 365일까지 cal값을 확인해 0이 아니면 연속된 일정에 속한 날일 것이므로 max와 비교해 최대 일정 갯수를 구하고 0이라면 현재 확인한 날의 전날이 연속된 일정의 종료날짜이므로 end가 i - 1이 되고 start부터 end까지가 연속된 일정이고 max가 그 연속된 일정의 최대 일정 갯수이므로 max * (end - start + 1)이 현재 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기가 되므로 이 값을 answer에 더한다. 그 후 연속된 일정의 시작날짜는 날짜를 순서대로 확인했을 때 일정갯수가 0인 날짜의 다음날이 될 것이므로 start에 i + 1을 대입하고 연속된 일정이 끝났으니 max를 0으로 초기화해준다.
이에 따라 365일까지 연속된 일정을 확인하면 연속된 일정의 종료날이 365일인 연속된 일정을 제외한 나머지 연속된 일정의 경우를 모두 확인하므로 max값을 확인해 이 값이 0이 아니라면 365일이 종료날짜인 연속된 일정이 있는 것이므로 이 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기도 구해서 answer에 더한다.
여기까지의 과정을 거치면 모든 연속된 일정에 대한 각 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기의 합을 answer에 저장한 것이므로 이 값을 출력하면 정답이 된다.
소스 코드
import java.util.StringTokenizer
fun main(){
val N = readLine()!!.toInt()
val cal = IntArray(366){0}
repeat(N){
val st = StringTokenizer(readLine())
for(i in st.nextToken().toInt()..st.nextToken().toInt()){
cal[i]++
}
}
var start = 1
var end = 0
var max = 0
var answer = 0
for(i in 1..365){
if(cal[i] == 0){
end = i - 1
answer += max * (end - start + 1)
max = 0
start = i + 1
} else {
max = maxOf(max, cal[i])
}
}
if(max != 0){
answer += max * (365 - start + 1)
}
println(answer)
}