코딩 챌린지 8일차 : 2096번 내려가기(G5)

이서진·2024년 9월 16일

DP python 백준

눈높이 개발 코딩 챌린지 - 기본반B

목록 보기

8/13

2096 : 내려가기 - 문제 링크

1. 문제 탐색하기

입력

n 줄의 수
numbers[3] 각 줄 별로 적혀있는 숫자

구하고자 하는 것

얻을 수 있는 최대 점수와 최소 점수
최대 DP의 마지막 값 중 최댓값, 최소 DP의 마지막 값 중 최솟값

알고리즘 설계

DP[n]은 n번째 줄까지 내려갔을 때 가능한 최대 점수이고,
초항 DP[0]은 첫번째 줄의 값이다.

DP[n][0]이 최대가 되려면 DP[n - 1][0]과 DP[n - 1][1] 중 더 큰 값에 n번째 줄의 첫번째 값이 더해져야 한다.
DP[n][1]이 최대가 되려면 DP[n - 1][0]과 DP[n - 1][1]과 DP[n - 1][2] 중 더 큰 값에 n번째 줄의 두번째 값이 더해져야 한다.
DP[n][2]이 최대가 되려면 DP[n - 1][1]과 DP[n - 1][2] 중 더 큰 값에 n번째 줄의 세번째 값이 더해져야 한다.

따라서 최댓값 점화식은
DP[n] = max(DP[n - 1] 중 가능한 위치) + n 이다.

같은 원리로 최솟값 점화식은
DP[n] = min(DP[n - 1] 중 가능한 위치) + n 이다.

7일차의 RGB거리 문제와 유사한데,
최대, 최솟값을 모두 구해야 하기 때문에 입력받은 배열의 수정이 불가능하고,
메모리 제한이 있기 때문에 이차원 DP 배열을 사용할 수 없다는 차이점이 있다.

그렇다면 입력을 받자마자 DP 계산을 수행해
일차원 DP 배열을 사용하는 방법으로 해결 가능하다.

시간복잡도

n까지의 DP를 탐색함 -> $O(n)$
1 $\leq$ n $\leq$ 100,000이므로 시간 내에 통과 가능

2. 코드 설계하기

n input 받기
DP를 위한 초항 설정
n번째 줄까지 한 줄씩 input을 받으며 최대, 최솟값 DP 계산

3. 시도 회차 수정 사항

1회차) i - 1번째까지의 합이 아니라 i - 1번째의 값으로 코드 작성
2회차) 성공!

4. 정답 코드

import sys
input = sys.stdin.readline

# input 받기
n = int(input())

# 초항 설정
dpmax = list(map(int, input().split()))
dpmin = dpmax[:]

for i in range(1, n):
    # 한 줄씩 받을 때마다 계산
    numbers = list(map(int, input().split()))
    
    # 최댓값
    dp = dpmax[:]
    dpmax[0] = max(dp[0], dp[1]) + numbers[0]
    dpmax[1] = max(dp[0], dp[1], dp[2]) + numbers[1]
    dpmax[2] = max(dp[1], dp[2]) + numbers[2]

    # 최솟값
    dp = dpmin[:]
    dpmin[0] = min(dp[0], dp[1]) + numbers[0]
    dpmin[1] = min(dp[0], dp[1], dp[2]) + numbers[1]
    dpmin[2] = min(dp[1], dp[2]) + numbers[2]

print(max(dpmax), min(dpmin))