제이슨의 개발이야기
백준 20207번 달력 코틀린Kotlin 본문
https://www.acmicpc.net/problem/20207
20207번: 달력
수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장
www.acmicpc.net
달력 성공
1 초 | 512 MB | 1746 | 787 | 594 | 44.864% |
문제
수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.
여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.
- 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
- 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.
- 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.
달력은 다음과 같은 규칙을 따른다.
- 일정은 시작날짜와 종료날짜를 포함한다.
- 시작일이 가장 앞선 일정부터 차례대로 채워진다.
- 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
- 일정은 가능한 최 상단에 배치된다.
- 일정 하나의 세로의 길이는 1이다.
- 하루의 폭은 1이다.
![](https://blog.kakaocdn.net/dn/b2ps5D/btrT3oUz1S1/B5ESqpYnFKJvUaCHrczEJK/img.png)
위의 그림에서와 같이 일정이 주어졌다고 하자. 여기서 코팅지의 면적은 아래의 파란색 영역과 같다.
![](https://blog.kakaocdn.net/dn/NtwJV/btrT4R2QYAy/yN7MJekgHaKpb2lncxWfd0/img.png)
이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다.
일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.
입력
첫째 줄에 일정의 개수 N이 주어진다. (1 ≤ N ≤ 1000)
둘째 줄부터 일정의 개수만큼 시작 날짜 S와 종료 날짜 E가 주어진다. (1 ≤ S ≤ E ≤ 365)
출력
코팅지의 면적을 출력한다.
예제 입력 1 복사
7
2 4
4 5
5 6
5 7
7 9
11 12
12 12
예제 출력 1 복사
28
예제 입력 2 복사
5
1 9
8 9
4 6
3 4
2 5
예제 출력 2 복사
36
풀이
위에 1번 예제를 배열로 표현해봤습니다
이 문제는 시작점과 ~ 끝나는 지점 사이에 몇개가 겹치는지 배열에 저장한 후
0이 나오기 전까지 배열의 요소 중 가장 큰 값이 사각형의 세로로 계산합니다
배열로 표현하는 방법을 생각하느냐 못하느냐에 따라서 쉽게 푸느냐 못푸느냐 결정될 문제 인거 같습니다 ^^
즉 2일 부터 9일 까지 배열의 인자값이 0이 아닌 정수가 있으므로
가로의 길이는 8이 되고
배열의 인자 값 중 가장 큰 값이 3이므로
세로의 길이는 3이 됩니다
그래서 첫번째 사각형의 넓이는 24가 되고
다시 11일 부터 12일 까지 배열의 인자 값이 0이 아닌 정수가 있으므로
가로의 길이는 2
세로의 길이는 2 이므로
넓이는 4가 됩니다
그 이후 365일까지 모든 인자값은 0이 되므로
24+4 =28이 됩니다
import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.max
fun main(){
var scanner = Scanner(System.`in`)
var arr = IntArray(375){0}
var N = scanner.nextInt()
var list = ArrayList<Point>()
var start = -1
var height = 0
var answer = 0
for(i in 0 until N){
list.add(Point(scanner.nextInt() , scanner.nextInt()))
}
list.sort()
for(i in list.indices){
var point = list.get(i)
for(j in point.start ..point.end){
arr[j] = arr[j]+1
}
}
for(i in 1 .. 367){
if(arr[i]!=0 && start == -1){
start = i
height = arr[i]
}else if(arr[i]==0 && start!=-1){
answer += (i - start)*height
start = -1
height = 0
}
if(height<arr[i]){
height = arr[i]
}
}
println(answer)
}
class Point(var start : Int , var end : Int): Comparable<Point>{
override fun compareTo(other: Point) : Int{
return (other.end- other.start) - (this.end- this.start)
}
}
'알고리즘' 카테고리의 다른 글
백준 2608 로마 숫자 Kotlin (1) | 2022.12.01 |
---|---|
백준 13424 비밀 모임 Kotlin 다익스트라 (0) | 2022.11.25 |
백준 17070 파이프 옮기기 Kotlin (0) | 2022.11.25 |
백준 17827 달팽이 리스트 코틀린[kotlin] (0) | 2022.11.24 |
프로그래머스 소수찾기 2단계 코틀린 완전탐색 (0) | 2021.09.21 |