BOJ(백준) 3020[개똥벌레]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 3020번을 풀어보겠습니다. 이 문제는 동굴을 통과하는 장애물들을 피하기 위해 최소한의 충돌 횟수를 계산하는 문제입니다. 석순과 종유석의 높이를 고려하여 최적의 경로를 찾아보겠습니다.

 

1. 문제 설명

주어진 동굴의 높이와 장애물의 위치를 이용하여, 동굴을 통과할 때 최소한의 충돌 횟수를 계산하는 문제입니다. 석순과 종유석의 높이를 누적합 배열을 이용하여 최적의 경로를 구합니다.

 

2. 접근법

1. 입력받기: 동굴의 높이(H)와 장애물의 개수(N)를 입력받습니다.

2. 장애물 데이터 입력: 각 장애물의 높이를 입력받아 석순과 종유석을 구분하여 배열에 저장합니다.

3. 누적합 배열 초기화: 장애물의 누적합을 계산하여 저장할 배열을 초기화합니다.

4. 누적합 계산: 장애물의 위치에 따라 누적합을 계산하여 prefix 배열에 저장합니다.

5. 최소 충돌 횟수 계산: 누적합 배열을 이용하여 최소 충돌 횟수와 그 횟수를 가지는 높이의 개수를 계산합니다.

6. 정답 출력: 최소 충돌 횟수와 그 횟수를 가지는 높이의 개수를 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# N: 장애물의 개수, H: 동굴의 높이
N, H = map(int, input().split())

# 누적합을 저장할 배열 초기화
prefix = [0] * (H + 1)
# 장애물 개수를 저장할 배열 초기화
grid = [0] * H

# 장애물 데이터 입력
for i in range(N):
    height = int(input())
    if i % 2 == 0:
        # 석순인 경우 (홀수 번째 장애물)
        grid[0] += 1
        grid[height] -= 1
    else:
        # 종유석인 경우 (짝수 번째 장애물)
        grid[H - height] += 1

# 누적합 계산
for i in range(H):
    prefix[i+1] = prefix[i] + grid[i]

# 첫 번째 요소는 제외 (prefix 배열을 1부터 시작)
prefix = prefix[1:]

# 최소 충돌 횟수와 그 횟수의 개수 계산
print(min(prefix), prefix.count(min(prefix)))

 

4. 코드 설명

1. 입력받기

• N과 H를 입력받아 장애물의 개수와 동굴의 높이를 설정합니다.

2. 장애물 데이터 입력

• 각 장애물의 높이를 입력받아 석순과 종유석을 구분하여 grid 배열에 저장합니다.

3. 누적합 배열 초기화

• prefix 리스트를 사용하여 누적합 배열을 초기화합니다. 이 배열은 (H+1) 크기로 설정하여 인덱스 계산을 용이하게 합니다.

4. 누적합 계산

• 장애물의 위치에 따라 누적합을 계산하여 prefix 배열에 저장합니다.

5. 최소 충돌 횟수 계산

• 누적합 배열을 이용하여 최소 충돌 횟수와 그 횟수를 가지는 높이의 개수를 계산합니다.

6. 정답 출력

• 최소 충돌 횟수와 그 횟수를 가지는 높이의 개수를 출력합니다.

 

**** 누적합 계산의 의미 **** 

+1과 -1을 통해 특정 구간의 시작과 끝을 표시하는 방식은 구간 업데이트를 간단하게 처리할 수 있는 효율적인 방법입니다. 이제 이를 통해 누적합(prefix sum)을 계산하면 각 높이에서 석순과 종유석의 영향을 쉽게 알 수 있습니다.

 

예시를 통한 설명

 

가령, 동굴의 높이가 5이고 다음과 같은 장애물이 주어진다고 가정해봅시다:

 

• 석순의 높이가 3인 장애물이 하나 있습니다.

• 종유석의 높이가 2인 장애물이 하나 있습니다.

 

이 경우, grid 배열을 다음과 같이 업데이트합니다:

 

1. 석순의 시작과 끝을 표시:

• grid[0] += 1  → grid = [1, 0, 0, 0, 0]

• grid[3] -= 1  → grid = [1, 0, 0, -1, 0]

2. 종유석의 시작을 표시:

• grid[H - height] += 1  → grid[5 - 2] += 1  → grid[3] += 1  → grid = [1, 0, 0, 0, 0]

 

누적합 계산

 

이제 누적합(prefix sum) 배열을 계산합니다. 각 높이에서의 장애물 개수를 계산하기 위해 누적합을 사용합니다.

prefix = [0] * (H + 1)
for i in range(H):
    prefix[i + 1] = prefix[i] + grid[i]

 

계산 결과는 다음과 같습니다:

• prefix[1] = 1

• prefix[2] = 1

• prefix[3] = 1

• prefix[4] = 0

• prefix[5] = 0

 

최종적으로 prefix 배열은 각 높이에서의 장애물 개수를 나타냅니다

• prefix = [0, 1, 1, 1, 0, 0]

**************************

 

5. Github으로 확인

coTest/BOJ/BOJ01_03_05_3020.py at main · pcy4196/coTest