9465

9465번 파이썬

처음에 이 문제를 풀을 때 뜯을려고 하는 스티커의 왼쪽 부분을 전부 다 검사해서(인접 변 제외) max인 값을 현재 스티커 값과 더해서 dp를 만들려고 했는데 답은 잘 나오는데 시간 초과 에러가 떴다..아마 시간 복잡도가 n^2이라 그런것 같다. 그래서 생각한 다른 방법은 만약 첫번째 행의 3번째 스티커를 뜯었다고 가정할때 (보기에선 100값 스티커) 두번째 행의 2번째와 첫번째 dp값 중 최대값만 계산해서 현재 스티커 값에 플러스 해주는 방식이다. 이걸 코드로 나타내면 아래와 같고 이런 방식을 이용하는 이유는 현재 스티커 값을 최대로 뜯을려고 하기 때문에 이웃한 변 다음칸을 뜯는게 효율적이지만 값이 그 옆에꺼가 더 클 경우가 그게 더 효율적일 수 있기 때문이다. 그리고 현재 col-3한 값을 구하는 것..