[백준/파이썬] 3020: 개똥벌레

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

3020번: 개똥벌레

문제 요약 : 석순과 종유석으로 가득찬 동굴이 있다. 동굴의 길이는 N미터, 높이는 H미터이다. 석순과 종유석의 크기가 주어진다. 개똥벌레는 모든 장애물(석순과 종유석)을 파괴하며 전진한다. 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간의 개수를 구하라.

 

예제 입력1 :

6 7
1
5
3
3
5
1

예제 출력1 :

2 3

 

📌 풀이 1)

예제1

예제 1의 장애물을 나타내면 위와 같다

이를 up과 down으로 나누어서  저장한다.

 

down 저장하는 것을 예로 들겠다.

 

down[i]는 i높이에서 종유석에 부딪히는 장애물의 개수이다.

이는 누적합을 통해서 구할 수 있다.

 

1. 길이가 1인 종유석은 개똥벌레가 높이 1에서 전진할 경우 무조건 부딪히게 된다.

그렇기 때문에 down[1]에 1을 넣어준다.

 

위와 같은 원리로 종유석의 높이들을 for문을 돌려서 각각의 높이에 1씩 넣어준다.

 

2. 개똥벌레는 i 높이의 종유석 외에 i높이보다 큰 종유석도 부딪힌다.

예를들어 높이1로 전진할 경우에는 종유석 높이 1, 3, 5에 모두 부딪히게 된다.

 

3. 이를 계산하기 위해서는 뒤에서부터 확인해야한다.

down[7]은 가장 높게 날 경우이기 때문에 확인해줄 필요가 없다.(자신높이만큼의 장애물 외에는 존재하지 않음)

down[6]은 자신 높이만큼의 장애물과 자신보다 큰 장애물을 더해주어야한다. (0+0)

down[5]는 자신 높이만큼의 장애물과 자신보다 큰 장애물을 더해주어야한다. (1+0)

down[4]는 자신 높이만큼의 장애물과 자신보다 큰 장애물을 더해주어야한다. (0+1)

...

 

down[i]는 자신 높이만큼의 장애물과 자신보다 큰 장애물을 더해주어야한다. (down[i] + down[i+1])

 

누적값으로 주어지기때문에 바로 뒤의 장애물들만 확인해주면 된다.

 

 

up 또한 down과 마찬가지로 구하면 된다.

여기서 중요한 것은 up은 down과 달리 위에서부터 시작된다는 것이다.

 

현재 up은 down과 동일하게 저장되어있다.

up만 생각하고 장애물을 계산하였을 때에는 문제없지만, down과 합쳐서 장애물의 개수를 세어주어야 하기 때문에 up을 다시 뒤집어주어야한다.

즉, 높이를 이와 같이 위에서부터 1이라고 생각하고 계산을 해주어야한다.

이를 적용하기 위하여

 

# tmp : 높이가 i일 때 부딪히는 장애물의 수(종유석과 석순 모두)
tmp = up[H-i+1] + down[i]

로 변환하여 장애물의 개수를 더해준다.

 

높이별로 가장 작은 장애물의 수를 갱신해주거나 개수만을 더해주는 식으로 비교하여 답을 추출한다.

# 개똥벌레
import sys
input = sys.stdin.readline

N, H = map(int,input().split())
up = [0]*(H+1)
down = [0]*(H+1)

for i in range(N):
    tmp = int(input())
    if i%2 == 0 :
        down[tmp] += 1
    else:
        up[tmp] += 1

for i in range(H-1,0,-1):
    up[i] += up[i+1]
    down[i] += down[i+1]
min_count = 0
min_num = sys.maxsize

for i in range(1,H+1):
    tmp = up[H-i+1] + down[i]
    if min_num == tmp :
        min_count += 1
        continue
    if min_num > tmp :
        min_num = tmp
        min_count = 1

print(min_num, min_count)

 

📌 풀이 2)

두번째는 bisect를 이용하는 방법이다.

bisect는 개똥벌레 풀이를 찾아보다가 알게 된 내용이다.

bisect_left(arr, value)
bisect_right(arr, value)

위와 같이 사용할 수 있으며, 해당 함수들은 각 리스트에서 특정 값이 삽입될 인덱스를 반환한다.

 

예를 들어 bisect_left([0,1,2], 3)의 경우 return값은 3이 된다.

이를 통해 현재 높이에 영향을 주지 않는 장애물의 개수를 구할 수 있다.

 

여기서 중요한 점은 리스트가 정렬되어 있어야 한다는 것이다.

# 개똥벌레
from bisect import bisect_left
import sys
input = sys.stdin.readline

N, H = map(int,input().split())
up, down = [], []

for i in range(N):
    tmp = int(input())
    if i % 2 == 0:
        down.append(tmp)
    else:
        up.append(tmp)

up.sort()
down.sort()

min_num = sys.maxsize
min_count = 1

for i in range(1, H+1):
    up_idx, down_idx = bisect_left(up, (H+1)-i), bisect_left(down, i)
    now_cnt = N - (up_idx + down_idx)
    
    if now_cnt < min_num:
        min_num = now_cnt
        min_count = 1
        
    elif now_cnt == min_num:
        min_count += 1
            
print(min_num, min_count)