[백준] 3020번 개똥벌레

사용 언어 - Python3

문제 -  3020번 개똥벌레 (골드 5)

3020번: 개똥벌레

 

정답

이모스법, prefix 누적합 문제 (정답 맞춘 여부 O)

1. 이모스법

https://imoz.jp/algorithms/imos_method.html

막대의 시작 = +1

막대의 끝 = -1

prefix 누적합 구하면 겹치는 수 구할 수 있다.

 

 

2. 석순과 종유석

range(0,n) for문을 반복하면서

짝수라면 = 석순 = 왼쪽에 붙어있음 = 시작은 항상 0  line[0] += 1 끝은 길이에 따라 line[석순길이] -= 1

홀수라면 = 종유석 = 오른쪽에 붙어있음 = 시작은 전체에서 종유석 길이 뺀 곳에서 line[전체길이-종유석길이] += 1

 

 

3. prefix

누적합을 구하고 맨 앞의 0은 무시해준다.

 

 

4. output

min(prefix)인 개수를 출력한다.

prefix.count(min(prefix))

 

import sys
input = sys.stdin.readline

n, h = map(int,input().split())
line = [0 for _ in range(h)]

for i in range(0,n):
    height = int(input())
    # 시작1, 끝 -1
    if i % 2 == 0:
        line[0] += 1
        line[height] -= 1
    else:
        line[h-height] += 1

prefix = [0 for _ in range(h+1)]
for i in range(h):
    prefix[i+1] = prefix[i] + line[i]

prefix = prefix[1:]
print(min(prefix), prefix.count(min(prefix)))

 

 

 

레퍼런스

• 정답 깃허브
• https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/3020_%EA%B0%9C%EB%98%A5%EB%B2%8C%EB%A0%88.py