1. 문제
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.
아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)
이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.
위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)
하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.
동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.
3. 출력
첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.
4. 예제 입력 / 출력
6 7
1
5
3
3
5
1
2 3
14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3
7 2
5. 풀이 과정
입력을 석순과 종유석을 번갈아 입력받는데 이를 잘 고려해야 한다.
다음은 n=2, h=5, 그리고 1, 3 을 입력받았을 때의 동굴의 형태이다. 보다시피 석순은 밑에서부터 1의 길이만큼 존재하지만 종유석은 천장에서부터 3의 길이만큼 존재하기 때문에 석순은 구간 1 을 지나갈 경우 부딪히고 종유석은 구간 3~5 을 지나갈 때 부딪힌다.
석순과 종유석을 각각의 리스트에 담아 정렬한다면 이분탐색을 통해 해당 문제를 풀어볼 수 있다. 예를 들어 다음 입력을 받는다고 가정해 보자.
6 7
1
5
3
3
5
1
이를 석순과 종유석 리스트에 담는다면 이런 형태가 될 것이다.
석순 = [ 1, 3, 5 ], 종유석 = [ 5, 3, 1 ]
또 이를 정렬한다면 이런 형태가 될 것이다.
석순 = [ 1, 3, 5 ], 종유석 = [ 1, 3, 5 ]
2번째 구간에서 부딪히는 장애물을 셀 때, 석순은 길이가 2이상인 장애물이라면 부딪히게 된다. 이 때, 이를 lower_bound 이분 탐색을 통해 부딪히는 장애물의 개수를 구할 수 있다.
# 찾고자 하는 값 이상이 처음 나타나는 위치를 구함
def lower_bound(array, target):
start, end = 0, len(array)
while start < end:
mid = (start + end) // 2
if target <= array[mid]:
end = mid
else:
start = mid + 1
return startlower_bound 와 uppper_bound 의 자세한 설명은 여기를 참고해 보자.
해당 함수에서 lower_bound(석순, 2) 를 호출하게 된다면 2이상의 값이 처음나오는 인덱스인 1을 반환할 것이다. 이 때 석순은 정렬되어 있어 인덱스 1 이후의 석순은 길이가 2 이상이기 때문에 지나갈 경우 모두 부딪히게 될 것이다. 따라서, 2번째 구간에서 부딪히는 석순의 개수는 석순의 총 개수 - lower_bound(석순, 2) 로 구할 수 있다.
2번째 구간을 지나갈 때 부딪히는 종유석의 개수는 반대로 생각해서 종유석의 총 개수 - lower_bound(종유석, 동굴의 높이 - 2) 로 구할 수 있다.
# 찾고자 하는 값 이상이 처음 나타나는 위치를 구함
def lower_bound(array, target):
start, end = 0, len(array)
while start < end:
mid = (start + end) // 2
if target <= array[mid]:
end = mid
else:
start = mid + 1
return start
n, h = map(int, input().split())
tites,mites = [], []
for _ in range(n // 2):
tites.append(int(input()))
mites.append(int(input()))
tites.sort()
mites.sort()
obs_cnt = [0] * h
for i in range(len(obs_cnt)):
# 해당 구간에 있는 종유석과 석순의 개수를 구함
obs_cnt[i] = n // 2 - lower_bound(tites, i + 1) + n // 2 - lower_bound(mites, h - i)
print(min(obs_cnt), obs_cnt.count(min(obs_cnt)))전체 코드는 다음과 같다.
6. 문제 링크
