백준 - 주간 달력 - 22936 - swift

 

https://www.acmicpc.net/problem/22936

22936번: 주간 달력

 

 

완전 탐색 및

누적합

 문제 유형 같다.  ( 알고리즘 유형에는 구간합이 없었지만, 내가 난이도 기여해서 누적합을 추가했다 ) 

나름 재밌었던 문제다!

 

문제의 지문이 조금 애매한 것 같은데.. 

( 그래도 풀 수 있었으니 ) 

 

 

우선 핵심 지문들이 있다. 

주력 하나에 들어갈 수 있는 일정의 개수는 제한이 없고, 
N개의 주력은 서로 연속되어야 한다. 주력의 맨 처음 날짜는 1 이상이어야 하고, 요일은 신경 쓰지 않는다. 일정은 테이프를 이용하여 나타내는데, 하나의 일정을 나타내기 위해 불필요하게 테이프를 자르는 경우는 없다고 하자. 예를 들면 하나의 일정을 하나의 주력에 표시할 때 여러 조각으로 나누어 붙이지 않는다는 것이다

이로써, 주력은 무조건 연속적이어야 한다는 점을 알 수 있다. 

 

테이프가 주력의 면적을 가장 많이 차지할 때 , 테이프를 자르는 횟수를 구해보자. 만약 테이프가 주력의 면적을 가장 많이 차지하는 경우가 2개 이상이라면, 해당하는 경우 중에 주력의 시작 날짜가 가장 작을 때의 테이프를 자르는 횟수를 구하자. 

 

N개의 주력이 연속이면서, 그 안에 테이프의 면적이 가장 많이 차지할 때를 찾는다. 

즉 일정이 가장 많이 포함된 이 아니라, 테이프의 면적이 요인이다. 

 

 

다시 보니, 이렇게 핵심 지문들만 파악했다면 금방 풀 수 있는 문제 같다. 

 

테이프의 면적을 구하기 위해서는, 누적합을 이용한다.  - times 배열을 이용

우선 시작 날짜 s , 끝 날짜 e라고 하면,

times [ s ] += 1 

times[ e + 1 ] -= 1을 해준다. 

 

이를 결과적으로 times [ x ] = 날짜가 X일 때, 1일부터 X일 때까지의 총테이프의 면적 수를 

만들고자 한다.

 

우선, 연속된 테이프를 의미하기 위해 

1부터 5만까지 for문을 돌면서 times를 초기화해주고, 

for i in 1...50000 {
    times[i] = times[i-1] + times[i]
}

다시 똑같이 for문을 돌면, 

for i in 1...50000 {
    times[i] = times[i-1] + times[i]
}

우리가 원하는 times [ x ]가 완성된다. 

 

 

그럼 이제, 1일부터 돌면서, N개의 주력만큼의 범위를 잡아서, 테이프의 총면적수를 list배열에 넣어준다. 

 

그리고 이를 지문에 있는 조건처럼 정렬시켜, 하나만 뽑고, 

 

해당 날짜로부터, 지문에 나와있듯이 테이프를 자르는 방법을 계산하면 된다.

테이프를 자르는 방법을 구현하기 위해, 

minus라는 누적합을 사용했다. 

어차피 테이프를 자른 것은, 끝 날짜 일 때와, 주력 끝 날짜 일 때이다. 

 

let N = Int(readLine()!)!
let M = Int(readLine()!)!
var times = Array(repeating: 0, count: 50001+(N*7))
var minus = Array(repeating: 0, count: 50001+(N*7))
for _ in 0..<M {
    let inp = readLine()!.split(separator: " " ).map{Int(String($0))!}
    times[inp[0]] += 1
    times[inp[1]+1] -= 1
    minus[inp[1]+1] += 1
}

for i in 1...50000 {
    times[i] = times[i-1] + times[i]
}
for i in 1...50000 {
    times[i] = times[i-1] + times[i]
}

var list = [(Int, Int)]()
for i in 1...50000 {
    list.append((i, times[i+(N*7)-1]-times[i-1]))
}

list.sort(by: {$0.1 == $1.1 ? $0.0 < $1.0 : $0.1 > $1.1})
let date = list.first!.0
var ans = 0
for i in 0..<N {
    let s = (i*7)+date
    for j in s+1..<s+7 {
        ans += minus[j]
    }
    ans += times[s+6] - times[s+5]
}
print(ans)