[BOJ] 2096번 - 내려가기

solved.ac 에서 클래스 관련해서 새롭게 업데이트 되면서, 단계별로 문제를 풀어보는 중이다.

마땅히 좋은 문제들이 없고, 대부분 포스트 했던 문제이거나 쉬운 구현 문제들 이었기 때문에 오늘에야 블로그를 쓰게 된다.

 

이번에 풀어볼 문제는 간단한 dp 문제였고, 메모리만 잘 해결하면 되는 문제였다.

메모리에 관해서 블로그 글을 쓴 적이 없다고 생각해서 이번 글을 적게 되었다.

 

www.acmicpc.net/problem/2096

2096번: 내려가기

 

프로그래머스에서 비슷한 문제를 풀어 봤던 것 같다. 각 행을 내려가면서 max, min 값을 잘 업데이트 해주면 되는 문제이다.

메모리가 4MB이기 때문에 (입력배열 : 10만*3*4byte + dp 저장배열 : 10만*3*4byte) 를 잡고 풀었더니 메모리 초과가 나왔다.

 

1. 메모리가 4MB인 것을 고려해 dp[] 크기를 줄일 방법을 생각해본다.

 

2. 각 행의 최적의 해를 어떤식으로 구할 수 있을까?

 

 

D에 올 값

1번째 행에 A,B,C 값들이 있다고 가정해보자.

D에 있는 값은 어떻게 될 수 있을까? 역으로 생각해보면 A, B둘 중 하나의 값이 올 수 있는 것을 알 수 있다.

이렇게 생각해보면 나머지 부분도 똑같이 될 것이다.

 

E에 올 값

F에 올 값

 

내가 A, B둘 중 최댓값을 고르는 것은 D,E,F 밑의 행에 영향을 끼치지 않는다.

내가 A를 선택하고 D에 왔을경우 밑의 수들은 A를 선택했기 때문에 어떤 것을 할 수 없거나 그런 제약을 받지 않는다.

그렇기 때문에 dp[]배열은 이전의 것만 계속해서 가지고 있으면 될 것이다.

이 전전의 것들은 다음 값을 입력받는데 아무 영향을 끼치지 않기 때문이다.

 

from sys import stdin

std = stdin.readline

N = int(std())

row = []

for i in range(N):
    row.append(list(map(int, std().split())))

dp = list(row[0])

ma, mi = max(dp), min(dp)


def solution():
    global dp, ma, mi
    for i in range(1, N):
        a, b, c = dp[0], dp[1], dp[2]
        dp[0] = max(a, b) + row[i][0]
        dp[1] = max(a, b, c) + row[i][1]
        dp[2] = max(b, c) + row[i][2]

    ma = max(dp)
    dp = row[0]
    for i in range(1, N):
        a, b, c = dp[0], dp[1], dp[2]
        dp[0] = min(a, b) + row[i][0]
        dp[1] = min(a, b, c) + row[i][1]
        dp[2] = min(b, c) + row[i][2]
    mi = min(dp)
    return ma, mi


solution()

print(ma, mi)