[백준] 2096 내려가기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

행이 아래로 진행이 될때마다 최댓값과 최솟값을 기억하며 내려가야 하므로 다이나믹 프로그래밍을 이용하였습니다.

 

초기에 문제를 접했을때, 주어진 모든 숫자들을 2차원 배열에 저장하였고 최댓값과 최솟값을 저장하는 3차원 배열의 리스트를 생성하였습니다. 그리고 각 행을 진행하면서 행별 최댓값과 최솟값을 저장하였습니다.

그러나 N의 범위가 최대 100,000으로 최악의 경우에 메모리 초과가 발생하였습니다.

 

그로 인하여 3차원 배열 DP를 3*2 크기의 2차원 배열로 변경하였습니다. 또한, 주어진 모든 숫자를 입력받은 후 계산을 진행하지 않고, 숫자가 주어질때 바로바로 연산을 진행하여 숫자들을 저장하는 변수를 사용하지 않게 진행하여 문제를 해결하였습니다.

2) 알고리즘

• 다이나믹 프로그래밍

3) 풀이 코드

사용 언어 - Python

import sys

N = sys.stdin.readline().split()

test 코드

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

2096번: 내려가기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다