[BOJ] 2096 내려가기 - python

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

2096번: 내려가기

풀이

처음에는 모든 루트를 다 도는 dfs로 생각했다. 모든 경우를 다 거쳐야 최소,최대 값을 얻을 수 있다고 생각했기 때문 또, dp 테이블을 이용해야겠다고 생각했을 때 dp테이블을 (맵의 크기)인 (3*N) 크기로 만들어서 진행했었는데, 옳지 않은 생각이었다. (물론 메모리부족이 뜨기도 했겠지만 N이 100,000 이기 때문에) → 각 맵의 줄에서 아래로 내려오면서 최소,최대를 만드는 문제인데 dfs방식으로 한 루트를 모두 훑고 다른 줄을 가는 상황에서 이전에 저장해 놓은 dp테이블로 인해 오답이 나왔다. → 할거면 한 루트를 모두 훑는 dfs방식이 아니라 한 줄을 (가로 줄) 모두 거치는 방식으로 진행해야 한다. (위에서 아래로 갈 때 해당 맵이 끝난 후 dp테이블을 저장하는 방식이기 때문에) BUT! 이 문제를 자세히 보면 각 위치마다 다음에 갈 수 있는 곳이 정해져 있는데, 그러면 그냥 각 줄에서 최대,최소를 선택하고 다음으로 진행하는 것이 최선인 것을 확인할 수 있다. (Greedy하게) ⇒ 위에서 아래로 내려가면서, 내려갈 수 있는 위치에 대한 조건이 걸려져 있는 상황이므로 Greedy하게 한 줄 씩 비교해가며 최대,최소 값을 완성시킨다. 또, N개 배열을 모두 저장해 놓으면 4MB 메모리를 만족시키지 못한다. 따라서 한 줄 씩 입력받아가며 알고리즘을 진행하자. 첫 번째 줄은 ans_max, ans_min에 각각 저장해 놓는다. 이후 각 줄을 돌면서 그 줄 각 위치(0,1,2)에서의 Greedy한 최대,최소 값을 구한다. 이를 바로 ans에 저장하지 않고 tmp를 만들어서 여기다가 저장한 후 마지막에 저장함 (계속 ans값을 사용하기 때문) 각 위치에서 이전 줄에서 올 수 있는 위치의 ans값 들 중 max,min을 구하고 거기에 해당 위치의 값을 더한다. line[i] 각 줄이 끝났을 때 ans를 갱신하고 다음 줄로 고고한다. 모든 줄이 끝난 후 ans가 가능한 최대, 최소 값들이고 이들의 max,min을 구하면 정답 뿅

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())

firstLine = list(map(int,input().split(" ")))
ans_max,ans_min = firstLine, firstLine #첫 번째 줄 입력받기

for _ in range(N-1): #각 줄 돌리기
    line = list(map(int,input().split(" ")))
    tmp_max,tmp_min = [0,0,0],[0,0,0]

    #==========한 줄에 대해서(한 단계) 0,1,2 각각 다 하기==========
    tmp_max[0] = max(ans_max[0],ans_max[1]) + line[0] #이전 것에서 최대인 것 택하고 + 현재 자신의 위치 값 더하기
    tmp_min[0] = min(ans_min[0],ans_min[1]) + line[0] #         최소

    tmp_max[1] = max(ans_max[0], ans_max[1], ans_max[2]) + line[1]
    tmp_min[1] = min(ans_min[0], ans_min[1], ans_min[2]) + line[1]

    tmp_max[2] = max(ans_max[1], ans_max[2]) + line[2]
    tmp_min[2] = min(ans_min[1], ans_min[2]) + line[2]
		#========================================================

    ans_max, ans_min = tmp_max, tmp_min #각 줄마다 ans 갱신

print(max(ans_max),min(ans_min))

얻어가는 것

• 메모리 부족

→ 모든 줄을 저장하려 하지 말고 한 줄 씩 해결할 수 있는 문제라면

→ 한 줄,한 줄을 입력받아가며 (덮어씌우면서) 문제를 푼다.

⇒ 메모리가 매우 작은데 100,000줄이면 한 줄 씩 입력 받아 풀 수 있는 문제인지 확인하기

# N <= 100,000일 때, 모든 것을 저장해버리면 메모리 4MB제한을 통과하지 못한다.
lines = [list(map(int, input().split(" "))) for _ in range(N)] 

• 위에서 아래로 진행할 때 결과만 저장하면 되는 경우에는 루트가 아니라, 값만 저장하면 되므로 dp 테이블을 대폭 줄여서 사용가능하다.

느낀점

"211126"

소요 시간 : 3h이상

• 와 메모리초과 빡세넹,, 한 번에 저장하면 안되고 입력 받으면서 풀어야만 하는 경우는 처음 봤다.
• 또 위에서 아래로 진행한다고 해서 무조건 위→아래 방향으로 생각하지 말고, 아래를 오기 위해 위는 누구누구가 있지? 를 생각할 수 있다는 점을 깨달았다. \
• 후 진짜 너무 빡세다 어려워.. for문 헷갈려..dfs bfs dp 연습..필요..