BAEKJOON 1932
문제
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
나의 처음 코드
선택된 수들의 합이 마지막에 최대가 되기 위해서는, 여러 후보들의 과정들을 담고 있어야 시간초과가 나지 않는다는 아이디어로 시작했다. 그래서 한층 한층 내려갈떄 마다 리스트의 크기를 늘려가면, 후보들을 리스트안에 넣어주었다. 밑에 쓴 코드로 예시를 따지자면, dp_list에 맨 꼭대기에서 아래로 내려갈 때 마다 최대가 될 수 있는 후보들을 넣어주고, 아니면 -1 값을 넣어줌으로써 갱신을 해주었다. 코드는 다음과 같다.
N = int(input())
num_list = [list(map(int, input().split())) for i in range(N)]
# print(num_list)
dp_list = [[num_list[0][0]+num_list[1][0], num_list[0][0]+num_list[1][1]]]
# print(dp_list)
for i in range(2, N):
tmp_list = []
idx = 0
cnt = 0
for j in dp_list[0]:
if j != -1:
if j + num_list[i][idx] > j + num_list[i][idx+1]:
tmp_list.append(j+num_list[i][idx])
tmp_list.append(-1)
idx += 1
else:
tmp_list.append(-1)
tmp_list.append(j+num_list[i][idx+1])
idx += 1
else:
tmp_list.append(-1)
tmp_list.append(-1)
dp_list.clear()
dp_list.append(tmp_list)
print(max(dp_list[0]))
결과는 메모리 초과. 공식을 세우면서 느낀거지만 당연히 메모리 초과가 난다는 것을 예감했다,,, n층에는 2의 n승으로 커지기 떄문이다. 2의 500승은 상상도 하기 싫은 숫자일 것이다… 자, 그러면 방식을 바꿔서 생각해보자.
새로운 리스트로 메모리를 낭비하기 보다, 비슷한 방식으로 주어진 메모리를 이용하면 어떨까???! 코드는 아래와 같다.
N = int(input())
num_list = [list(map(int, input().split())) for i in range(N)]
for i in range(N-1, 0, -1):
for j in range(i):
if num_list[i][j] > num_list[i][j+1]:
num_list[i-1][j] += num_list[i][j]
else:
num_list[i-1][j] += num_list[i][j+1]
print(num_list[0][0])
일단 결과는 맞았습니다. !!. 아까랑 다른 점을 눈치채겠는가!? 새로운 리스트를 만드는 것이아니라, 입력값을 받은 리스트에서 아래로 내려가면서, 더해주면서 바꾸는 것이다. 간단한 예시를 들자면,
1
2 4 저렇게 구성되어 있을 경우 다음 단계는
1
3 5 이런식으로 더해지면서 바뀌는 것이다. 조건은 더할 수 있는 것중에 큰것을 더하면된다. 그러면 제일 아래에 남는 숫자들을 후보들의 집합이 되는 것이다. 그러면 최대 메모리는 N(N-1)/2 가 되므로 아까보다 더 절약할 수 있게 된다!!