[백준] 내려가기 (2096번)

난이도 : Gold5
Link : https://www.acmicpc.net/problem/2096
Tag : 다이나믹 프로그래밍, 슬라이딩 윈도우
풀이일자 : 2024년 9월 16일

📌 문제 탐색하기

N: 줄의 개수

조건

즉 0번째 인덱스일 경우 0번째와 1번째 인덱스를 다음번에 가질 수 있고
1번째 인덱스일 경우 0, 1, 2
2번째 인덱스일 경우 1, 2 를 다음번에 가질 수 있다.

가능한 시간복잡도

시간복잡도 상 N의 개수는 100,000이므로 문제는 없어보이나 메모리 제한이 4mb로 되어 있는것으로 보아 기존 DP로 누적 값들을 계속 저장하고 있으면 메모리가 초과 될 것으로 보인다.

따라서 이 문제는 DP 와 슬라이딩 윈도우를 이용하여 접근해야한다.

📌 문제 접근 방법

슬라이딩 윈도우란 ?

창문 틀을 밀어서 창문을 이동시키는 알고리즘이다.
즉 정해진 배열 크기 내에서 배열의 위치만 바꿔서 값들을 배열에 저장하는 DP 방법 중 하나이다.

예를들어 지금까지 DP 문제들은 DP라는 배열에 0번째 인덱스부터 N 번째 인덱스까지 저장하였지만 슬라이딩 윈도우를 이용하면 정해진 규칙 내에서 윈도우 틀을 만들고 틀의 배열의 크기만큼 누적 값을 더해서 이동하는 방식이다.

이런 방법을 적용시키기 위해

grid 배열에 얻을 수 있는 점수들을 저장할 것이고
줄이 바뀔 때 마다 grid배열을 초기화하여 메모리를 절약할 예정이다.

최대값을 저장할 dp_max 배열과 최솟값을 저장할 dp_min배열을 만들어 각 줄마다 얻을 수 있는 최대 점수와 최소 점수를 배열로 저장할 예정이다.

📌 코드 설계하기

1. n을 입력 받는다.
2. grid의 첫째줄을 입력받는다.
3. 첫째줄의 값들을 dp_max와 dp_min에 초기화 시켜 첫째줄에서 얻을 수 있는 점수를 저장한다.
4. 둘째줄부터 N번째 줄까지 반복문을 통해 dp_max와 dp_min을 초기화한다

dp_max = [grid[0] + max(dp_max[0],dp_max[1]), grid[1] + max(dp_max[0], dp_max[1], dp_max[2]), grid[2] + max(dp_max[1], dp_max[2])]
 dp_min = [grid[0] + min(dp_min[0],dp_min[1]), grid[1] + min(dp_min[0], dp_min[1], dp_min[2]), grid[2] + min(dp_min[1], dp_min[2])]

다음과 같이 초기화를 진행한다.
0번째 인덱스로 이동할 경우 그전 0번째, 1번째에서 오는 경우 중 max 또는 min
1번째 인덱스로 이동할 경우 그전 0번째, 1번째, 2번째 에서 오는 경우 중 max 또는 min
2번째 인덱스로 이동할 경우 그전 1번째, 2번째에서 오는 경우 중 max 또는 min

5. dp_max와 dp_min 에서 max와 min값을 출력한다.

📌 시도 회차 수정 사항

틀렸습니다. (1%)

n = int(input())

grid = list(map(int, input().split()))
dp_max = grid
dp_min = grid

for i in range(n-1):
    grid = list(map(int,input().split()))
    dp_max = [dp_max[0] + max(grid[0],grid[1]), dp_max[1] + max(grid[0], grid[1], grid[2]), dp_max[2] + max(grid[1], grid[2])]
    dp_min = [dp_min[0] + min(grid[0],grid[1]), dp_min[1] + min(grid[0], grid[1], grid[2]), dp_min[2] + min(grid[1], grid[2])]

print(max(dp_max), min(dp_min))

dp_max 와 dp_min을 초기화 시켜주는 과정에서 max 또는 min에서 gird를 선택하게 한다면 두번째 행부터 현재의 모든 값을 고려하지만 과거의 모든값까지 고려하지 않기 때문에 dp_max와 dp_min을 gird와 바꿔주었다.

📌 정답 코드

n = int(input())

grid = list(map(int, input().split()))
dp_max = grid
dp_min = grid

for i in range(n-1):
    grid = list(map(int,input().split()))
    dp_max = [grid[0] + max(dp_max[0],dp_max[1]), grid[1] + max(dp_max[0], dp_max[1], dp_max[2]), grid[2] + max(dp_max[1], dp_max[2])]
    dp_min = [grid[0] + min(dp_min[0],dp_min[1]), grid[1] + min(dp_min[0], dp_min[1], dp_min[2]), grid[2] + min(dp_min[1], dp_min[2])]

print(max(dp_max), min(dp_min))