2096번 파이썬

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

2096번: 내려가기

이 문제의 정답률이 낮은 이유는 풀이 방식은 쉬운데 메모리 초과 문제 때문인것 같다.

나도 첨에 dp리스트를 전부 다 만들었더니 메모리 초과가 떠서 다른 방법으론 아래와 같은 방법을 사용했다.

문제 풀이 방식은 다음 줄의 dp와 이전줄의 dp에 다음줄 해당 인덱스 ary값을 더하는 방식을 이용했다.

maxp[i+1][y]=max(maxp[i+1][y],maxp[i][j]+ary[i+1][y])
minp[i+1][y]=min(minp[i+1][y],minp[i][j]+ary[i+1][y])

하지만 이처럼 dp 전체 리스트를 이용하면 메모리 초과가 뜨게 된다

그래서 다음행으로 넘어갈때마다 새로운 temp리스트를 만들어서 dp의 다음줄 역할을 할 수 있게 했다

이때 temp리스트의 값은 min 경우 최솟값이 900000이 될 수 있으므로 900001로 초기화하였고 마찬가지로 max도 그것을 반대로 생각해서 -1로 초기화 하였다

그랬더니 pypy로 제출했을 때 메모리 초과 에러가 뜨지 않는다.

import sys
input = sys.stdin.readline
n=int(input())
ary=[list(map(int,input().split())) for _ in range(n)]
maxp=[ary[0][0],ary[0][1],ary[0][2]]
minp=[ary[0][0],ary[0][1],ary[0][2]]
dx=[-1,1,0]
for i in range(n-1):
  maxt=[-1,-1,-1]
  mint=[900001,900001,900001]
  for j in range(3):
    for idx in range(3):
      y=j+dx[idx]
      if 0<=y<3:
        maxt[y]=max(maxt[y],maxp[j]+ary[i+1][y])
        mint[y]=min(mint[y],minp[j]+ary[i+1][y])
  maxp=maxt
  minp=mint
print(max(maxp),min(minp))