(백준/파이썬) 3020호: 반딧불(imos 알고리즘)

쉬운 목차

1. 문제

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

3020호:반딧불이

'추천 관련글,

반딧불이가 장애물(석순과 종유석)로 가득한 동굴에 들어갔습니다. 동굴의 길이는 N미터, 높이는 H미터입니다. (N은 짝수) 첫 번째 장애물은 항상 석순, 그 다음은 종유석과 석순

www.acmicpc.net

두 번째 솔루션

코알라 이야기를 듣고 풀었던 문제입니다. 사실 문제는 해결책을 미리 알면 해결됩니다.

– 먼저 누적 합계를 사용해 보았습니다. Obstacle 이라는 이름의 배열에 있는 모든 장애물을 구한 후 높이가 i 일 때 imos 배열에 있는 장애물의 수를 확인했습니다.

– 이제 imos 알고리즘을 다룰 차례입니다.

imos 알고리즘은 탑승과 하차만 기록하는 알고리즘입니다. 누적 합을 효율적으로 사용하는 알고리즘입니다.

알고리즘에 대한 설명은 좀 더 간단한 언어로 표현할 수 있도록 공부한 후 별도의 글로 자세하게 작성하도록 하겠습니다.

장애물이 들어오면 imos 알고리즘에 의해 진입 시 +1, 퇴장 시 -1이 부여됩니다.
* 이때 석순은 위아래로 밀랍하는 과정을 반복한다는 점에 유의해야 한다.
n개의 장애물이 있으므로 for 문을 n번 회전시켜 0,2,4…번째 석순이 0~h구간을 드나들며,
1,3,5.. 붕재 석순은 호에서 h까지 출입한다.
imos 알고리즘을 적용하여 imos 배열을 만듭니다.
배열의 끝을 버리십시오! 마지막 배열의 최소값과 최소값의 수를 반환합니다.

3. 코드

import sys
input = sys.stdin.readline

n, h = map(int,input().split())

imos = (0)*(h+1)

for i in range(n):
    o = int(input())
    if i % 2==0:
        imos(0)+=1
        imos(o)-=1
    else:
        imos(h-o) +=1
        imos(h) -=1

now = 0
for i in range(h):
    now+=imos(i)
    imos(i) = now

Min =min(imos(0:h))
print(Min,imos.count(Min))

4. 잊지 말자

** 잘못된 응답 코드 !

import sys
input = sys.stdin.readline

n, h = map(int,input().split())

obstacle = (int(input()) for _ in range(n))
imos = (0)*(h)
# 짝수, 홀수일 때 다름

for o in range(n):
    #홀수번째
    if o%2 == 0:
        #imos(0:obstacle(o)) += 1
        for i in range(obstacle(o)):
            imos(i) +=1
    else :
        for i in range(h-obstacle(o),h):
            imos(i)+=1

print(min(imos), imos.count(min(imos)))

줄지어 있는 장애물 사이로 어떤 것은 1단계, 어떤 것은 2단계, 어떤 것은 3단계… 이렇게 보여줬습니다.

하지만 sys로 입력 시간을 줄이려고 해도 시간 초과가 나타납니다!

입력이 길면

import sys
input = sys.stdin.readline

코드를 유용하게 사용합시다!

(출처 및 참조)

https://velog.io/@nkrang/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-imos-%EB%B2%95 https://openai.com/blog/chatgpt

한국항공대학교 알고리즘학회 코알라 “Bronze to Platinum” 강의 자료.