[백준] 3020 개똥벌레 by 누적합 (Python)

내 풀이1 > 메모리 초과

# 17:33~17:53
# 풀리긴 하는데 메모리 초과

# 위아래 번갈아서 하고 합의 최솟값 구하면 되는거 아닌가?
# 이차원 행렬로 1로 채우고 행의 합 구하면 될듯.
import sys
sys.stdin=open("input.txt", "r")
input=sys.stdin.readline

# 종유석 세우기
def solution():
  for i in range(n):
    hight=bar[i]
    if i%2==0:
      for j in range(hight):
        cave[(h-1)-j][i]=1
    else:
      for j in range(hight):
        cave[j][i]=1
  # 파괴할 거 구하기
  destroy_sum=[]
  for i in range(h):
    tmp=sum(cave[i]) # 각 행의 합
    destroy_sum.append(tmp)
  min_v=min(destroy_sum)

  #최소 격파할 값 총 몇개나 있는지
  cnt=0
  for x in destroy_sum:
    if x==min_v:
      cnt+=1
  print(min_v, cnt)
    


if __name__=="__main__":
  n, h=map(int, input().split())
  cave=[[0]*n for _ in range(h)]
  bar=[]
  for _ in range(n):
    bar.append(int(input().rstrip()))
  solution()

내 풀이2 > 시간 초과

# 17:33~17:53
# 풀리긴 하는데 시간 초과

# 위아래 번갈아서 하고 합의 최솟값 구하면 되는거 아닌가?
# 이차원 행렬로 1로 채우고 행의 합 구하면 될듯.
import sys
sys.stdin=open("input.txt", "r")
input=sys.stdin.readline

# 종유석 세우기
def solution():
  destroy_sum=[] # 개똥벌레(행)마다 destroy해야할 개수 > 0번부터 h-1까지. 위에서부터.
  for i in range(h): # 몇번째 개똥벌레(행)
    tmp=0
    for j in range(n):
      hight=bar[j]
      if j%2==0:
        if hight>=(i+1):
          tmp+=1
      else:
        if h-hight<=i:
          tmp+=1
    destroy_sum.append(tmp)
  # 파괴할 거 구하기
  
  min_v=min(destroy_sum)

  #최소 격파할 값 총 몇개나 있는지
  cnt=0
  for x in destroy_sum:
    if x==min_v:
      cnt+=1
  print(min_v, cnt)
    


if __name__=="__main__":
  n, h=map(int, input().split())
  bar=[]
  for _ in range(n):
    bar.append(int(input().rstrip()))
  solution()

문제점

곧이 곧대로 이차원 배열 만들어서 풀면 메모리 초과, 그렇다고 이차원 배열 만들지 않고 일일이 사이즈 비교하면 시간초과.

시간초과 예상

(2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
그럼 N>= 100,000으로 볼 수 있다.

1초당 다음과 같다.

N 범위	시간복잡도 O( )
500	N3
2,000	N2
100,000	N*logN
10,000,000	N

그럼 시간 복잡도가 최대 O(N)이어야 하는데, 여기서는 O(N2) 이므로 시간초과 될 것이다.

모범답안

# 모범답안
import sys
input = sys.stdin.readline

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

# 누적합 이용
lines = [0] * h

for i in range(n):
    high = int(input())
    # 석순
    if i % 2 == 0:
        lines[h - high] += 1
    # 종유석
    else:
        lines[0] += 1
        lines[high] -= 1
        
# 누적합
for i in range(1, h):
    lines[i] += lines[i - 1]
    
# 최소값 체크 및 최소값 갯수 체크
count = 0
low = min(lines)
for i in lines:
    if i == low:
        count += 1
        
print(low, count)

풀이

시작 부분과 끝부분을 lines에 +=1 과 -=1로 표시한다. 누적합을 할 때 밑에서부터 하기 때문에, 1) 홀수일 땐 아래서부터 시작하니까 lines[0]+=1; lines[high]-=1로 처음과 끝 부분을 표시한다. 2) 짝수일 땐 어차피 마지막까지(맨 위까지) 막대기가 존재하니까 lines[high-h]+=1로 더해주고 만다. 그래서 lines[i] += lines[i - 1]로 누적합을 하면 겹쳐져 있는 송판 개수가 나온다.

idea

송판 부수기 같은 이미지:
일일이 다 계산하지 말고, 처음과 끝 부분을 일차원 배열에 +=1과 -=1로 표시해서 누적합해주자.

모범답안 보고 수정한 내 풀이

# 모범답안 보고 수정한 내 풀이
import sys
sys.stdin=open("input.txt", "r")
input=sys.stdin.readline

# 증가하는 곳, 감소하는 곳 체크
def solution():
  cave=[0]*h
  for i in range(n):
    high=bar[i]
    if i%2==0:
      cave[h-high]+=1
    else:
      cave[0]+=1
      cave[high]-=1
  # 누적합 구하기
  for i in range(h-1):
    cave[i+1]+=cave[i]

  # 최소값과 그 빈도 구하기
  min_v=min(cave)
  cnt=0
  for x in cave:
    if x==min_v:
      cnt+=1
  print(min_v, cnt)

if __name__=="__main__":
  n, h=map(int, input().split())
  bar=[]
  for _ in range(n):
    bar.append(int(input().rstrip()))
  solution()