3020 - 개똥벌레
📌 문제
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.
아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)
이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.
위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)
하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.
동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.
📋 코드
N, H = map(int, input().split())
cave = [int(input()) for _ in range(N)]
up = [0] * (H+2)
down = [0] * (H+2)
result = [0] * (H+2)
for i in range(N):
height = cave[i]
if i % 2 == 0:
down[height+1] += 1
else:
up[H - height] += 1
for i in range(2, H+1):
down[i] += down[i-1]
for i in range(H, -1, -1):
up[i] += up[i+1]
for i in range(1, H+1):
result[i] = up[i] + down[i]
print(N-max(result), result.count(max(result)))💡 한마디
- down : 각 높이에 해당하는 석순이 몇 개 있는지 저장
- down[2] = 3 이라면 동굴 내부에 높이 2짜리 석순이 3개 있다는 뜻
- up : 각 (동굴 높이 - 종유석 높이) 해당하는 종유석이 몇 개 있는지 저장
- 동굴 높이가 5, up[2] = 4 라면 높이 3짜리 종유석이 4개 있다는 뜻
개똥벌레가 지나가는 구간의 높이가 올라갈수록 통과할 수 있는 석순은 많아지고, 종유석은 적어진다. 따라서 각 높이마다 통과할 수 있는 종유석과 석순의 수를 메모이제이션을 통해 갱신시켜가며 풀었다.
