백준 20207 달력 Kotlin (누적 합)

문제 출처 : https://www.acmicpc.net/problem/20207

20207번: 달력

문제

 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 

여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.

• 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
• 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다. 
• 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.

달력은 다음과 같은 규칙을 따른다.

• 일정은 시작날짜와 종료날짜를 포함한다.
• 시작일이 가장 앞선 일정부터 차례대로 채워진다.
• 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
• 일정은 가능한 최 상단에 배치된다.
• 일정 하나의 세로의 길이는 1이다. 
• 하루의 폭은 1이다. 

위의 그림에서와 같이 일정이 주어졌다고 하자. 여기서 코팅지의 면적은 아래의 파란색 영역과 같다.

이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다. 

일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.

입력

첫째 줄에 일정의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄부터 일정의 개수만큼 시작 날짜 S와 종료 날짜 E가 주어진다. (1 ≤ S ≤ E ≤ 365)

출력

코팅지의 면적을 출력한다.

알고리즘 분류

• 구현
• 그리디 알고리즘
• 정렬

풀이

그냥 주어진 n개의 일정 모두 s~e범위를 +1 해 주어 해당 범위의 최대 높이와 가로길이를 구해주어도 풀리는 문제지만, 본인은 최근에 풀었던 누적 합을 일괄 적용하는 기술을 적용해봤다.

2022.05.27 - [알고리즘 문제 풀이/프로그래머스] - 프로그래머스 파괴되지 않은 건물 Kotlin (누적 합)

위 문제는 카카오 블라인드 문제이다.

필자가 적용한 누적 합의 기술은 위 문제의 공식 풀이에서 발췌했다.

간단히 설명하면,

0 2 2 2 1 1의 배열이 있다고 하자.

두 번째 값부터 네 번째 값까지 1을 더한다고 하면 위 배열에 0 1 1 1 0 0 배열을 더한 것과 같다.

위의 경우에선 각 인덱스끼리 매칭되어 더해지지만, 누적 합의 개념을 적용하면

+= 연산을 사용하여 이전 값들까지 더한다.

즉, 0 1 1 1 0 0을 누적 합에 적용할 배열로 표현하면

0 1 0 0 -1 0이 된다.

위 배열을 편의상 누적 합 배열이라고 하겠다.

위 배열에 누적 합을 해 보자.

0 1 1 1 0 0이 된다.

 

즉, s~e에 대한 정보가 주어질 때마다 원본 배열에 값을 더하는 것이 아니라, 누적 합 배열에 s~e 정보를 넣어놓고, 나중에 일괄적으로 원본 배열에 더해주는 것이다.

 

이후에는 그냥 원본 배열을 돌면서 x,y값을 구하면 된다.

x는 y가1 이상인 값이 처음 나올 때부터, y가 0이 나올 때까지 증가,

y는 x가 증가하는 동안 나온 y값 중에 최댓값,

y가 0이라면 x*y를 답에 더하고 x, y를 0으로 초기화.

원본 배열을 모두 탐색하고 x,y가 0이 아닌 수로 남아있다면 이 x*y도 더해주기

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()){
    //input
    val n = getInt()
    val calendar = IntArray(367)
    var end = 0
    repeat(n){
        //solve
        //누적 합 정보들을 모아뒀다가 한 번에 계산
        val (from, to) = getIntList()
        calendar[from]++
        calendar[to+1]--
        end = end.coerceAtLeast(to)
    }
    //preSum
    //누적 합 적용
    for(i in 1 .. end){
        calendar[i] += calendar[i-1]
    }
    //코팅지 면적 구하기 (0)나오면 계산
    var x = 0
    var y = 0
    var answer=0
    for(i in 1 .. end){
        if(calendar[i]==0){
            answer +=x*y
            x = 0
            y = 0
        }
        else{
            x++
            y = y.coerceAtLeast(calendar[i])
        }
    }

    write("${answer + x*y}")

    close()
}