[백준] 2096번: 내려가기

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

initial

a relatively textbook dp question. it is like that min. number of steps to reach a floor/storey.

But there was a memory limit, which I didn’t see properly. I used memoisation of size 3*n to store each max and min value for each grid but while the answer is right, it was rejected due to memory issues.

n = int(input())
Graph = [list(map(int, input().split())) for _ in range(n)]
Dp = [[(0, 0) for _ in range(n)] for _ in range(n)]

for i in range(n):
    Dp[0][i] = (Graph[0][i], Graph[0][i])

for i in range(1, n):
    for j in range(n):
        if j == 0:
            Dp[i][j] = (min(Dp[i - 1][j][0], Dp[i - 1][j + 1][0]) + Graph[i][j], 
                        max(Dp[i - 1][j][1], Dp[i - 1][j + 1][1]) + Graph[i][j])
        elif j == n - 1:
            Dp[i][j] = (min(Dp[i - 1][j][0], Dp[i - 1][j - 1][0]) + Graph[i][j], 
                        max(Dp[i - 1][j][1], Dp[i - 1][j - 1][1]) + Graph[i][j])
        else:
            Dp[i][j] = (min(Dp[i - 1][j][0], Dp[i - 1][j + 1][0], Dp[i - 1][j - 1][0]) + Graph[i][j], 
                        max(Dp[i - 1][j][1], Dp[i - 1][j + 1][1], Dp[i - 1][j - 1][1]) + Graph[i][j])


min_value = min(Dp[-1][j][0] for j in range(n))
max_value_last_row = max(Dp[-1][j][1] for j in range(n))
print(min_value)
print(max_value_last_row) 

Then, I tried refactoring the code to use just one dp list of size n like [(1,1), (2,2), (3,3)] but didnt work.

solution

Here we should use a sliding window technique, where we initialise 2 dp list of size 3 - maxDp and minDp which stores the maximum and minimum value for a given index from 0 to 2. We initialise these 2 dp lists with the first row. Then, the recursive formula is the same.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
maxDp = arr
minDp = arr

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

print(max(maxDp),min(minDp) )

complexity

n time and space

The provided code calculates the maximum and minimum values according to certain rules for a given set of inputs. Let's analyze the time and space complexity of the code:

Time Complexity:
1. Reading the initial input and creating the arr, maxDp, and minDp lists takes O(n) time, where n is the number of elements in the input list.
2. The code then enters a loop that iterates n - 1 times. In each iteration, it processes a set of inputs, performs operations on the maxDp and minDp lists, and updates them.
3. Inside the loop, there are operations that involve calculating the maximum and minimum values for each element in the maxDp and minDp lists based on the current input values. These operations are performed in constant time (O(1)) for each element in the lists.

The overall time complexity is O(n) for reading the initial input and O(n) for the loop, resulting in a final time complexity of O(n).

Space Complexity:
1. The code uses three lists: arr, maxDp, and minDp, each with n elements. Therefore, the space complexity for these lists is O(n).

Overall, the space complexity of the code is O(n).

In summary, the code has a time complexity of O(n) and a space complexity of O(n), making it efficient in terms of both time and space usage.