[파이썬/Python] 백준 2096번: 내려가기

숨·2024년 9월 16일

코테

알고리즘 문제 풀이

목록 보기

76/105

📌 문제 : 백준 2096번

📌 문제 탐색하기

N : 줄의 수 $(1 ≤ N ≤ 100,000)$

내려가기 게임을 하고 있다.
N줄에 0~9 사이 숫자가 3개씩 적혀 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 문제이다.

문제 풀이

⭐️ 내려가기 게임의 제약 조건

첫 줄에서 시작 → 마지막 줄에서 끝나는 놀이

처음의 3개 숫자 중 하나를 골라 시작

다음 줄 내려갈 수 있는 2가지 조건

바로 아래의 수로 넘어가기 ⭕️

바로 아래의 수와 붙어 있는 수로만 이동 ⭕️

위의 규칙에 따라 마지막 줄까지 내려왔을 때 최대 점수, 최소 점수를 구해야 한다.
모든 줄에서 최댓값, 최솟값을 얻도록 한다면 마지막 줄에서도 최댓값, 최솟값을 얻을 수 있을 것이다.
→ 앞의 결과를 이용할 수 있는 DP로 해결하도록 한다!

~~최대, 최소를 구해야 하기 때문에 DP 테이블 2개를 정의한다.~~
→ 🚨 이렇게 하면 메모리 초과가 발생하기 때문에 테이블에 따로 값을 저장하지 않고 매번 갱신하는 형태로 변경하였다.

💡 현재 위치한 줄의 3개의 칸은 제약 조건에 따라 각각 이전 줄의 다른 지점에서 올 수 있다.

이전 줄 1번째 칸 또는 2번째 칸 → 현재 1번째 칸

이전 줄 1번째 칸 또는 2번째 칸 또는 3번째 칸 → 현재 2번째 칸

이전 줄 2번째 칸 또는 3번째 칸 → 현재 3번째 칸

이와 같이 각각의 칸에 대해 여러 가지 경우가 존재한다.
한줄한줄 입력받을 때마다 현재 위치의 점수를 합했을 때 최대/최소가 되는 값으로 갱신해준다.
→ 마지막 줄까지 진행했을 때 최종으로 원하는 값을 구할 수 있도록 구현한다.

가능한 시간복잡도

N개의 줄마다 3가지 숫자를 이용해 최대/최소 갱신 → $O(N)$

최종 시간복잡도
$O(N)$ 으로 최악의 경우 $O(100,000)$ 이 되어 1초 내 연산이 가능하다.

알고리즘 선택

DP 테이블에 저장하지 않고 최대/최소 갱신하면서 구하기

📌 코드 설계하기

필요한 입력 받기
2개의 DP 테이블 정의
DP 테이블 초기화
for문을 통해 DP 테이블 같이 채우기
결과 출력

📌 시도 회차 수정 사항

1회차

# 각 줄의 점수 입력
scores = [list(map(int, input())) for _ in range(N)]

ValueError: invalid literal for int() with base 10: ' '
입력을 띄어쓰기 기준으로 쪼개서 리스트에 넣으려고 했는데 split()를 빼먹었다.

2회차

❌ 원래의 아이디어
현재 위치의 점수를 합했을 때 최대/최소가 되는 값을 DP 테이블에 넣어주면 된다!

1번째 칸에 대하여 점화식을 작성하면 다음과 같다.
max_dp[i][0] = max(max_dp[i-1][0], max_dp[i-1][1]) + scores[i][0] # 최댓값
min_dp[i][0] = min(min_dp[i-1][0], min_dp[i-1][1]) + scores[i][0] # 최솟값

for문을 통해 아래와 같이 값을 채워준다.
# DP 테이블 채우기
for i in range(1, N):
    # 첫번째 숫자 : 이전 줄의 첫번째 또는 두번째
    max_dp[i][0] = max(max_dp[i-1][0], max_dp[i-1][1]) + scores[i][0]
    # 두번째 숫자 : 이전 줄의 첫번째 또는 두번째 또는 세번째
    max_dp[i][1] = max(max_dp[i-1][0], max_dp[i-1][1], max_dp[i-1][2]) + scores[i][1]
    # 세번째 숫자 : 이전 줄의 두번째 또는 세번째
    max_dp[i][2] = max(max_dp[i-1][1], max_dp[i-1][2]) + scores[i][2]

    # 첫번째 숫자 : 이전 줄의 첫번째 또는 두번째
    min_dp[i][0] = min(min_dp[i-1][0], min_dp[i-1][1]) + scores[i][0]
    # 두번째 숫자 : 이전 줄의 첫번째 또는 두번째 또는 세번째
    min_dp[i][1] = min(min_dp[i-1][0], min_dp[i-1][1], min_dp[i-1][2]) + scores[i][1]
    # 세번째 숫자 : 이전 줄의 두번째 또는 세번째
    min_dp[i][2] = min(min_dp[i-1][1], min_dp[i-1][2]) + scores[i][2]
위와 같이 채워진 2개의 DP 테이블에서 마지막 값인 인덱스 N-1의 3가지 값 중 최대/최소의 값을 출력하면 원하는 답을 얻을 수 있다.

위와 같은 아이디어로 제출했는데 메모리 초과가 발생했다.
최댓값에 대한 DP 테이블, 최솟값에 대한 DP 테이블 2가지를 활용해 모든 경우의 수를 저장해서 발생한 문제같다. DP 테이블에 저장하지 말고 한줄 한줄 입력받을 때마다 계산하는 식으로 변경했다.

3회차

예제 입력1에 대한 출력이 32 23으로 잘못 나왔다.

값을 갱신할 때 아래와 같이 값을 갱신하는데 다음 숫자 계산 시 이용할 숫자를 이전에 변경해서 발생한 문제였다.

  # 최솟값 갱신
  # 첫번째 숫자 : 이전 줄의 첫번째 또는 두번째
  min_dp[0] = min(min_dp[0], min_dp[1]) + scores[0]
  # 두번째 숫자 : 이전 줄의 첫번째 또는 두번째 또는 세번째
  min_dp[1] = min(min_dp[0], min_dp[1], min_dp[2]) + scores[1]
  # 세번째 숫자 : 이전 줄의 두번째 또는 세번째
  min_dp[2] = min(min_dp[1], min_dp[2]) + scores[2]

인덱스 별로 따로 변경하지 않고 한번에 갱신하도록 변경하였다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N 입력
N = int(input())

# 첫번째 입력 받기
scores = list(map(int, input().split()))

# 초기값 설정
max_dp = scores
min_dp = scores

# 최대, 최소 갱신하기
for _ in range(N-1):
    # 이후 점수 입력 받기
    scores = list(map(int, input().split()))

    # 최댓값 갱신
    max_dp = [max(max_dp[0], max_dp[1]) + scores[0], max(max_dp[0], max_dp[1], max_dp[2]) + scores[1], max(max_dp[1], max_dp[2]) + scores[2]]

    # 최솟값 갱신
    min_dp = [min(min_dp[0], min_dp[1]) + scores[0], min(min_dp[0], min_dp[1], min_dp[2]) + scores[1], min(min_dp[1], min_dp[2]) + scores[2]]

# 결과 출력
print(max(max_dp), min(min_dp))