Enochkon's blog

문제

코드

import sys
import copy
input = sys.stdin.readline
n= int(input())
# dp배열을 쓰고 싶지만 메모리가 부족하여 현재층과 바로 위층에 사용한 배열만 초기화
bq=[[0,0],[0,0],[0,0]]
cq=[[0,0],[0,0],[0,0]]
for i in range(n):
    arr=list(map(int,input().split()))
    #최대값 구하기
    cq[0][0]=max(bq[0][0],bq[1][0])+arr[0]
    cq[1][0]=max(bq[0][0],bq[1][0],bq[2][0])+arr[1]
    cq[2][0]=max(bq[1][0],bq[2][0])+arr[2]

		#최소값 구하기
    cq[0][1]=min(bq[0][1],bq[1][1])+arr[0]
    cq[1][1]=min(bq[0][1],bq[1][1],bq[2][1])+arr[1]
    cq[2][1]=min(bq[1][1],bq[2][1])+arr[2]
    bq=copy.deepcopy(cq)
resMax=0
resMin=100000000
for i in range(3):
    resMax=max(resMax,max(bq[i]))
    resMin=min(resMin,min(bq[i]))
print(resMax,resMin)

풀이

• 간단한(하지만 조건있는) dp 문제
• 메모리가 굉장히 작으므로, 전체를 저장하는게 아닌 사용하는 부분을 계속 업데이트 하는 방식으로 푼다.

1. 높이 n을 입력받는다.
   • dp 문제이지만 여기서 메모리 크기가 4mb이다. 그러므로 층을 한층씩 내려가면서 본다.
   • 각 층에서 내려갈 수 있는 부분은 인접해 있는 부분이기 때문에 거꾸로 밑층에서도 인접한 곳에서만 올 수 있다.
   • 그러므로 dp[i][0] (왼쪽) : dp[i-1][0] (왼쪽 위), dp[i-1][1] (가운데 위) 중 하나 dp[i][1] (가운데쪽) : dp[i-1][0] (왼쪽 위), dp[i-1][1] (가운데 위), dp[i-1][2] (오른쪽 위) 중 하나 dp[i][2] (오른쪽) : dp[i-1][1] (가운데 위), dp[i-1][2] (오른쪽 위) 중 하나 이다.
   • 최소값과 최대값을 둘다 구하므로, 각각의 위치에 최소,최대를 둘다 구해서 표시해준다.
   • 현재 층(cq)과 바로 위층(bq)만을 사용하고, 다음 층으로 넘어가면 bq=cq로 업데이트 해준다.n만큼 한층씩 내려가면서 최대값과 최솟값을 기록하면서 내려간다.

2. 반복문을 전부 돌고, 1층에서의 최대값과 최소값을 찾아서 출력한다.

특이사항

• dp의 점화식은 대놓고 문제에서 그림으로 주지만, 메모리가 굉장히 제한적이여서 쉽지 않은 문제였다.
• dp배열을 cq와 bq로 바꿨는데도 메모리 초과→ 입력받는 arr도 한줄씩 받게 변경 → 시간초과가 나서 sys로 입력속도 빠르게함 → 성공