[백준 파이썬] 2096 내려가기

2096번: 내려가기

문제

3열로 이루어진 줄에서 주어진 N의 크기의 행으로 이루어져 있다. 각각의 칸 마다 숫자가 부여되고 위에서부터 칸을 내려갈 때 최대값과 최소값을 구하는 문제이다. 

이 때 내려갈 수 있는 조건은 자기자신과 인접해있는 2칸이내의 칸으로만 내려갈 수 있다. 즉 가장 측면의 칸일경우 바로 아래칸과 가운데 칸으로 이동할 수 있고 가운데 칸의 경우 모든 칸으로 내려갈 수 있다.

 

---

알고리즘

전체적인 아이디어는 이전에 풀었던 1149번 RGB거리와 유사하다. 따라서 Dp로 풀어야겠다고 생각했다.

 

풀이

minRes = copy.deepcopy(numbers)
maxRes = copy.deepcopy(numbers)​

최대값 최소값을 각각 구해야 하므로 각각의 결과를 담을 배열 2개를 생성하였다.

for i in range(1, N):
    for j in range(3):
        if j == 0:
            minRes[i][j] = min(minRes[i-1][0], minRes[i-1][1]) + minRes[i][j]
            maxRes[i][j] = max(maxRes[i-1][0], maxRes[i-1][1]) + maxRes[i][j]

        elif j == 2:
            minRes[i][j] = min(minRes[i-1][1], minRes[i-1][2]) + minRes[i][j]
            maxRes[i][j] = max(maxRes[i-1][1], maxRes[i-1][2]) + maxRes[i][j]

        else:
            minRes[i][j] = min(minRes[i-1]) + minRes[i][j]
            maxRes[i][j] = max(maxRes[i-1]) + maxRes[i][j]

위에서 언급한 아이디어를 이용하여 내려갈 수 있는 타일에 대해 각각의 경우의 수를 계산하여 최소값과 최대값을 계산 후 출력하였다.

 

하지만 이렇게 푸니 메모리가 초과하였다. 그 이유를 생각해보니 배열을 2개 생성하여 각각 값을 넣어서 그런것 같았다.

따라서 배열을 만들되 최소한의 값만 저장하는 방식으로 구현해야 했다.

 

maxRes = [0] * 3
minRes = [0] * 3

maxTmp = [0] * 3
minTmp = [0] * 3

for i in range(N):
    a, b, c = map(int, input().split())
    for j in range(3):
        if j == 0:
            minTmp[j] = min(minRes[j], minRes[j+1]) + a
            maxTmp[j] = max(maxRes[j], maxRes[j+1]) + a

        elif j == 1:
            minTmp[j] = min(minRes[j-1], minRes[j], minRes[j+1]) + b
            maxTmp[j] = max(maxRes[j-1], maxRes[j], maxRes[j+1]) + b

        else:
            minTmp[j] = min(minRes[j], minRes[j-1]) + c
            maxTmp[j] = max(maxRes[j], maxRes[j-1]) + c

    for j in range(3):
        maxRes[j] = maxTmp[j]
        minRes[j] = minTmp[j]

코드를 수정하여 임시값을 담을 배열과 실제값을 담을 배열을 생성하였다.

그 후 임시배열에 먼저 할당한 후 비교하여 실제 값을 저장하는 배열에 다시 할당하는 방식으로 변경하였다.

 

---

코드

N = int(input())

maxRes = [0] * 3
minRes = [0] * 3

maxTmp = [0] * 3
minTmp = [0] * 3


for i in range(N):
    a, b, c = map(int, input().split())
    for j in range(3):
        if j == 0:
            minTmp[j] = min(minRes[j], minRes[j+1]) + a
            maxTmp[j] = max(maxRes[j], maxRes[j+1]) + a

        elif j == 1:
            minTmp[j] = min(minRes[j-1], minRes[j], minRes[j+1]) + b
            maxTmp[j] = max(maxRes[j-1], maxRes[j], maxRes[j+1]) + b

        else:
            minTmp[j] = min(minRes[j], minRes[j-1]) + c
            maxTmp[j] = max(maxRes[j], maxRes[j-1]) + c

    for j in range(3):
        maxRes[j] = maxTmp[j]
        minRes[j] = minTmp[j]


print(max(maxRes), min(minRes))