[백준/Python] 3020번: 개똥벌레(imos 알고리즘)

1. 문제

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

3020번: 개똥벌레

 

2. 해결방법 

 

코알라 강의를 듣고난 후 푼 문제이다. 사실상 해결방안을 미리 알고 푼 문제 .. 

 

- 처음엔 누적합을 이용해보았다. obstacle이라는 배열을 두고 장애물을 모두 받은 뒤, imos배열에 (imos방식은 아닌데 왜 배열이름이 imos인가에 대해서는 너그럽게 양해해주시길 바란다.. ) 높이가 i일 때 obstacle이 몇개인지를 각각 알아보았지만 시간초과 ! 

 

- 이제 imos알고리즘으로 다루어볼 시간이다. 

imos알고리즘은 입장, 퇴장만을 기록하는 알고리즘이다. 누적합을 효율적으로 쓰는 알고리즘이다.

알고리즘에 대한 설명은 필자가 더 쉬운 언어로 표현할 수 있게 공부한 다음 따로 포스팅으로 자세히 작성해보겠다 .. 

 

• 장애물을 입력받고 imos알고리즘을 통해 입장 시 +1, 퇴장 시 -1을 해준다.
  * 이때 주의할 점은 석순이 위로, 아래로 자라는 것을 반복한다는 것이다. 
• n개의 장애물이 있으므로 for 문을 n번 돌리며 0,2,4... 번째 석순은 0~ h 구간에서 입장-퇴장, 
• 1,3,5.. 번재 석순은 h-o ~ 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)))

obstacle배열을 통해 높이 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%95https://openai.com/blog/chatgpt

한국항공대학교  알고리즘 학회 KOALA '브론즈에서 플래티넘' 강의자료