[Problem Solving] 백준 3020번 개똥벌레 파이썬

백준 3020번 개똥벌레 문제에 대한 해설과 코드입니다. 문제는 다음의 링크를 참고해주시기 바랍니다. 문제 해설

 

문제에서는 짝수 번째에서는 석순이 홀수 번째에서는 종유석이 등장합니다. 그렇기 때문에 석순과 종유석을 따로 계산하여 겹치는 장애물의 개수를 세워주어야 합니다. 문제 해결을 위한 과정은 다음과 같습니다.

 

1. 입력받은 n을 index로 사용하여 순서에 따라 석순과 종유석에 1을 넣어준다.
2. 석순은 0을 기준으로 오른쪽에 있는 값들을 모두 더해서 저장한다.
3. 종유석은 h를 기준으로 왼쪽에 있는 값들을 모두 더해서 저장한다.
4. 2, 3에 계산된 값을 answer에 더해서 저장한다.
5. answer에서 가장 작은 값과 가장 작은 값의 수를 출력한다.

2번과 3번의 계산 결과는 각 자릿수를 지나갔을 때 파괴되는 장애물의 수입니다. 따라서 4번에서는 자릿수에 맞게 값을 더해주는 것만으로 높이값에 따른 장애물 파괴 횟수가 저장되게 됩니다. 다음은 코드입니다.

 

# 백준 No.3020 개똥벌레
n, h = map(int, input().split(' '))

data = []
for i in range(n):
  data.append(int(input()))

answer = [0] * (h + 1)
top = [0] * (h + 1)
bottom = [0] * (h + 1)

count = 0
for number in data:
  if count % 2 == 0:
    count += 1
    top[number] += 1
  else:
    count += 1
    bottom[h-number+1] += 1

for i in range(h - 1, 0, -1):
  top[i] += top[i + 1]

for i in range(1, h + 1):
  bottom[i] += bottom[i-1]

for i in range(1, h + 1):
  answer[i] = top[i] + bottom[i]

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

 

위의 알고리즘을 시간복잡도를 계산해보면 평균의 경우에 O(n)의 시간 복잡도를 가지고, 최악의 경우에도 O(n)이 나오게 됩니다.