백준 3020 개똥벌레 파이썬 문제풀이 (python 누적합)

문제 보러가기

 

백준 개똥벌레 파이썬 문제풀이

동굴에 아래에서 올라오는 석순과 위에서 내려오는 종유석이 한 칸씩 번갈아 나온다.

이 중 하나의 높이에 고정해서 벌레는 뚫고 가는데,

가장 적게 장애물을 뚫는 곳의 개수와 몇 개를 뚫는지 구하는 문제이다. 

 

단순하게 생각하면 오른쪽으로 이동하면서

장애물의 누적 개수를 쌓아가며 최소인 칸들을 구하면 될 것 같은데

 

정말 신기한 방법이 다있다.

장애물이 시작되는 칸을 1이라고 하고, 끝난 다음칸을 -1로 설정한다.

 

	-1		-1
		-1
			1
	1
-1
1		1

예를 들어 그림의 경우 4까지의 길이만 표현해보면 이런 식이다.

원래 5칸인데, 가장 위의 칸은 여분으로 하나를 추가한 것이다.

 

위 숫자들을 더하면 아래-위 순서대로

2 -1 1 1 -1 -2 가 된다.

마지막 6번째는 무시하고

2 -1 1 1 -1 을 수열 누적합을 하면

 

2 1 2 3 2가 되는데,

이건 순서대로 장애물의 개수를 의미한다.

 

헉

이러한 방법은 이모스 법 이라는 방법이다.

신기한 방법인데 이대로 구현해보자. 

 

n,h = map(int, input().split())
accum = [0 for _ in range(h+1)]
for i in range(n):
    num = int(input())
    if i%2 == 0: # 짝수일 때 0~
        accum[0]+=1
        accum[num]-=1
    else: # 홀수일 때 1~
        accum[h-num] += 1
        accum[h] -= 1
# 누적합 구하기
for i in range(h):
    accum[i+1] += accum[i]
print(min(accum[0:-1]), accum.count(min(accum[0:-1])))

짝수 홀수를 나누어서 1, -1 범위를 배열에 계속 넣어주고,

누적합을 해서 각 높이마다 장애물이 몇 개 나오는지 구한다.

 

accum 배열은 크기를 하나 더 했으므로 [0:-1] 로 마지막 수를 제외했다.

하지만 틀렸고.

아무래도 accum 배열의 마지막 수 때문인 것 같다.

 

음.. 이제보니 acount를 세는 쪽이 잘못되었다. 

accum.count를 하면 -1적용이 안된 list에서 찾을 것이다. 

 

정답 코드

n,h = map(int, input().split())
accum = [0 for _ in range(h+1)]
for i in range(n):
    num = int(input())
    if i%2 == 0: # 짝수일 때 0~
        accum[0]+=1
        accum[num]-=1
    else: # 홀수일 때 1~
        accum[h-num] += 1
        accum[h] -= 1
# 누적합 구하기
for i in range(h):
    accum[i+1] += accum[i]

print(min(accum[0:-1]), accum[0:-1].count(min(accum[0:-1])))

count를 셀 때도 범위를 잡아주었다.

맞았다!