3020번: 개똥벌레 / gold 5 / 누적합

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

3020번: 개똥벌레

 

메모리 초과

'''
3020번: 개똥벌레 / gold 5
'''
import sys

input = sys.stdin.readline

# 1. 입력 받기 / graph 만들기
n, h = map(int, input().split())
graph = [[0 for _ in range(n)] for _ in range(h)]
for j in range(n):
    num = int(input())
    if j % 2 == 0:
        now = h - 1
        i = -1
    else:
        now = 0
        i = 1
    cnt = 0
    while cnt < num:
        graph[now][j] = 1
        now = now + i
        cnt += 1

min_res = int(1e9)
min_cnt = 0
for i in range(h):
    res = sum(graph[i])
    if min_res > res:
        min_res = res
        min_cnt = 1
    elif min_res == res:
        min_cnt += 1

print(min_res, min_cnt)

 

정답 코드

'''
3020번: 개똥벌레 / gold 5 / 누적합
'''
import sys

input = sys.stdin.readline

# 1. 입력 받기
n, h = map(int, input().split())
down = [0 for _ in range(h + 1)]
up = [0 for _ in range(h + 1)]

for i in range(n):
    v = int(input())
    if i % 2 == 0:
        down[v] += 1
    else:
        up[v] += 1

# 2. 누적합
for i in range(h - 1, 0, -1):
    down[i] += down[i + 1]
    up[i] += up[i + 1]

# 3. 최소 값 도출
min_res = int(1e9)
min_cnt = 0
for i in range(1, h + 1):
    tmp_res = down[i] + up[h - i + 1]
    if min_res > tmp_res:
        min_res = tmp_res
        min_cnt = 1
    elif min_res == tmp_res:
        min_cnt += 1

print(min_res, min_cnt)

 

Review

 

메모리 초과 코드

 

- graph를 모두 그린 후 / 높이 별로 sum() 을 사용하여 최솟 값을 구함

 

- 아마 graph가 매우 큰 경우, 메모리 초과가 발생 했을 것이라고 생각

 

 

 

정답 코드

 

#1. 입력 받기

- 석순과 종유석을 나누기 위해 up(종유석), down(석순) 리스트 만들기 (0~h 인덱스까지 범위)

- up, down리스트를 번갈아 가면서 부르기 + 입력 받은 장애물 크기(v)를 인덱스 번호로 참조한 값을 +1 해주기

 

 

#2. 누적합

(입력 받은 up, down 리스트 누적합 실행하기)

높이가 2이면, 2 이상의 높이를 가진 장애물들을 모두 거쳐간다는 의미

EX) down[2] = down[2]+down[3]+down[4]...+down[h]

 

- down[h-1] += down[h]  / down[h-2] += down[h-1] ... => for 문을 통해 해결

 

 

#3. 최소 값 도출

석순과 종유석은 장애물이 나는 것이 반대 인 것을 생각

높이가 1일때, down[1] + up[h] 

높이가 2일때, down[2] + up[h-1]

...

- tmp_res = down[i] + up[h-i+1]