[python] 백준 2096 - 내려가기
백준 2096 - 내려가기 [GOLD 5]
숫자 세 개의 입력이 n개 주어진다. (1 <= n <= 100,000)
인접한 대각선 또는 바로 아래의 수를 계속 더해나가
가장 밑으로 도달했을 때 가능한 최고의 수와 최저의 수를 출력하면 된다.
DP
DP 문제다.
특이한 점은 메모리가 제한이 빡빡하기 때문에,
list에 입력을 몰아 넣는 것만으로도 메모리 초과가 발생한다.
DP 답게 한 단계식 처리하면 되므로,
시작값 리스트 한 개를 할당한 후에,
이후 반복마다 리스트에 입력을 갱신하며 DP로 풀어나가면 된다.
그런데 이러한 정답 코드 방법을 쓰지 않고도 문제 해결 자체는 가능하다. (24/04/02 기준)
노잼 정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
n_l = list(map(int, input().split()))
dp_min = dp_max = n_l
for _ in range(n-1):
n_l = list(map(int, input().split()))
dp_min = [min(dp_min[0], dp_min[1]) + n_l[0],
min(dp_min) + n_l[1],
min(dp_min[1], dp_min[2]) + n_l[2]]
dp_max = [max(dp_max[0], dp_max[1]) + n_l[0],
max(dp_max) + n_l[1],
max(dp_max[1], dp_max[2]) + n_l[2]]
print(max(dp_max), min(dp_min))
Array를 활용해보자.
처음에 입력을 한번에 받고 무지성으로 코드를 짜면서,
어떻게 메모리 줄타기를 해볼 수 없을까, 잔머리를 굴려봤다.
사실 위의 방법이 훨씬 빠르고 메모리 소모도 적은 좋은 코드다. 아래는 그저 Array 자료형에 대한 이야기다.
Python에도 array가 있다!
Python에는 array 자료형(배열)이 없다고 생각하는 사람들이 꽤 있다.
사실 엄밀한 의미의 진짜 array는 없는 게 맞다.
다만 array와 상당수의 개념을 공유하며, 편의성이 조금 뛰어난 array 모듈이 있다.
동적으로 크기를 늘릴 수 있고, 자료를 삽입, 삭제, 추출이 자유롭다.
그래서 사실은 효율적인 숫자형 리스트라고 표현하는 게 맞긴 하다… (공식 문서에도 그렇게 적혀있다.)
1
2
3
4
import array
# 정수형 배열 생성
arr = array.array('i', [1, 2, 3]) # integer
상세한 사용법은 공식DOCS에서 확인하자! (한글 번역 되어있다.)
List와 array의 차이
통념상 list를 array 또는 배열이라고 퉁치긴 하지만, 엄연히 다른 자료형이다.
List는 매우 편리하지만 진짜진짜 무거운 자료형이다.
입력, 확장, 삭제가 매우 자유롭고, 자료형 내부에 여러 기본, 복합 자료형을 넣을 수 있다.
편의성을 위해서 성능이 상당히 저하된 자료형이다.
List는 객체의 메모리 주소를 저장한다.
그에 반해 array는 값 자체를 저장하기 때문에 같은 자료형만 들어갈 수 있다.
Python의 array 모듈은 이러한 속성을 갖고 있기 때문에
List나 tuple을 사용하는 것보다 메모리나 실행속도 면에서 효율적인 편이다.
특히, 이번 문제에서는 더욱 그렇다!
array를 활용하는 문제 풀이
다시 한 번 말하지만, 그냥 정답 코드가 훨씬 빠르고 메모리 소모도 적다.(이 문제에 대해서는)
아주 단순하게 말하자면, array를 사용할 경우 메모리를 절반 수준으로 줄일 수 있다.
이 문제의 제한 사항에 따라 최대한의 입력을 구현하여,
이를 각각 list와 array에 담을 경우 다음과 같은 결과가 나온다.
1
2
3
4
5
6
7
8
9
10
11
12
import array, sys, random
arr = array.array('i', [])
list = []
for i in range(100000):
x = random.randint(0, 9)
list.append(x)
arr.append(x)
print(sys.getsizeof(list)) >>> 800984
print(sys.getsizeof(arr)) >>> 408360
list는 기본적으로 정수형 자료에 4byte를 할당하지만,
array('i')의 경우, 2byte를 할당한다.
이 문제는 입력을 한 번에 받을 경우,
똑같은 객체를 하나 더 만들어야 해서 메모리 소모가 두 배가 된다!(이런 거지같은 풀이를 봤나!)
그렇기 때문에 list에 입력을 한 번에 넣어서는 반드시 메모리 초과가 발생하는 문제다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import array
n = int(input())
arr = array.array('i')
for _ in range(n):
arr.extend(list(map(int, input().split())))
arr2 = arr.__copy__()
def find_m(route, func, mv):
i = 1
while i < n:
for j in range(3):
m = mv
for k in range(-1, 2):
if 0 <= j + k < 3:
m = func(m, route[(i-1)*3+(j+k)] + route[i*3+j])
route[(i*3)+j] = m
i += 1
print(func(route[-3:]), end=' ')
find_m(arr, max, 0)
find_m(arr2, min, n*10)
느리고, 메모리는 많이 잡아먹고, 코드도 어렵다
array 모듈을 불러오는 것 자체가 약 5000kb를 먼저 먹어버린다.
결과적으로는 800kb 정도를 썼는데, 위의 계산에 거의 들어맞는다.
애초에 백준의 메모리 소모 기준을 잘모르긴 하지만…
어쨌든, array를 쓰면 정수형 list의 메모리를 절약할 수 있다는 걸 알아두자!
내 코드 같다