[백준 2096] 내려가기 [Python]

백준 2096 - 문제

백준 2096 - 입/출력

---

풀이

문제에서 주어진 규칙에 따라 N줄을 내려가면서 최댓값과 최솟값을 구하면 되는 문제다.

주어진 규칙을 살펴보자.

백준 2096 - 문제

별의 위치에 따라 더하거나 뺄수 있는 칸의 범위가 달라진다.

이번에는 아래 그림을 살벼보자

별이 기준이 아닌, 동그라미를 기준으로 각각 빨,초,파의 선을 그었다.

첫 번째 칸에 위치한 동그라미는 첫 번째와 두 번째의 별에 대해 더하거나 뺄 수 있다는 의미이다.

 

앞으로 계산해야되는 칸을 각각 max_dp, min_dp에 담아주자.

1번 줄은 그대로 담으면 된다.

2번 줄 부터 N번 줄까지는 위에서 말했듯 동그라미를 기준으로 계산하듯이 계산해주면 된다.

각각 max_dp와 min_dp를 구하는 코드이다.

코드가 너무 길다고 생각된다면 아래처럼 쌍으로 묶어주어 관리해도 된다.

dp[0] = [ [ board[0] + max(dp[0][0], dp[0][1]) ], [ board[0] + min(dp[0][0], dp[0][1]) ] ]

하지만 가독성이 떨어진다.

 

참고로 문제의 접근방식과는 큰 상관은 없지만 메모리 제한이 4MB이기 때문에

모든 줄에 대한 정보를 계속 저장하는 방식을 하면 메모리 초과가 발생한다.

어차피 한 번쓰고 다시 안쓸 각 줄마다의 초기 정보를 매번 새롭게 입력받는 방식으로 바꾸어 주자.

---

소스코드

소스코드 보기

---

출처

2096번: 내려가기