[BAEKJOON]2096 내려가기

문제 요약

• 알고리즘 분류: 동적계획법, dp
• 난이도: Gold5
• 문제내용:
  • 위에서 내려가는데 조건에 맞게 더하면서 내려가야한다.
    • 0: 0, 1
    • 1: 0, 1, 2
    • 2: 1, 2
  • 맨 밑에 값중 최소값과 최대값을 구해라

• 사이트: https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

문제풀이

 이번 문제는 동적계획법 관련 문제이다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다. dp문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게 풀수 있다. 일단 점화식 구하는 방법은 쉽다.

 

위 그림 처럼 위에 양쪽 인덱스중 가장 큰값, 작은 값을 각가 더하면서 내려가면 된다. 하지만 아래 코드처럼 최소값, 최대값 dp 구하기 위한 배열/리스트 만들면 메모리 초과가 나온다.

import sys
input = sys.stdin.readline

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
max_dp = [[0] * 3 for _ in range(N)]
max_dp[0][0] = matrix[0][0]
max_dp[0][1] = matrix[0][1]
max_dp[0][2] = matrix[0][2]

min_dp = [[0] * 3 for _ in range(N)]
min_dp[0][0] = matrix[0][0]
min_dp[0][1] = matrix[0][1]
min_dp[0][2] = matrix[0][2]

for i in range(1, N):
    max_dp[i][0] = matrix[i][0] + max(max_dp[i - 1][0], max_dp[i - 1][1])
    max_dp[i][1] = matrix[i][1] + max(max_dp[i - 1][0], max_dp[i - 1][1], max_dp[i - 1][2])
    max_dp[i][2] = matrix[i][2] + max(max_dp[i - 1][1], max_dp[i - 1][2])
    
    min_dp[i][0] = matrix[i][0] + min(min_dp[i - 1][0], min_dp[i - 1][1])
    min_dp[i][1] = matrix[i][1] + min(min_dp[i - 1][0], min_dp[i - 1][1], min_dp[i - 1][2])
    min_dp[i][2] = matrix[i][2] + min(min_dp[i - 1][1], min_dp[i - 1][2])
    
print(max(max_dp[N - 1]), min(min_dp[N - 1]))

문제 접근 방법

 최대 최소를 N개 만큼 만들지 않고 푸는 방법을 설명하겠다. 점화식은 기존과 같이 진행 하면된다. 거기에 추가하여 최대, 최소를 이전과 다음에 저장 할 배열을 만드면 된다.

값을 입력할때 마다 이전 값에서 최대, 최소값을 더한 후에 다음 진행할 값에 저장한후 연산이 끝나면 이전 값에 저장 하는식으로 진행하면된다. 이렇게 하면 배열은 2개만 사용하면 되기때문에 메모리 초과가 나오지 않을것이다.

Code

Python

 파이썬은 depcopy 깊은 복사로 처리하면 값에 의한 영향을 안받을수 있다.

import sys, copy
input = sys.stdin.readline

N = int(input())
max_dp = [list(map(int, input().split())), [0] * 3]
min_dp = [copy.deepcopy(max_dp[0]), [0] * 3]

# 입력할때 마다 dp 연산한다.
for i in range(1, N):
    x1, x2, x3 = map(int, input().split())
    
    # 최대값 dp 연산
    max_dp[1][0] = x1 + max(max_dp[0][0], max_dp[0][1])
    max_dp[1][1] = x2 + max(max_dp[0][0], max_dp[0][1], max_dp[0][2])
    max_dp[1][2] = x3 + max(max_dp[0][1], max_dp[0][2])
    
    # 최소값 dp 연산
    min_dp[1][0] = x1 + min(min_dp[0][0], min_dp[0][1])
    min_dp[1][1] = x2 + min(min_dp[0][0], min_dp[0][1], min_dp[0][2])
    min_dp[1][2] = x3 + min(min_dp[0][1], min_dp[0][2])
    
    # dp연산 끝난 후에 다시 이전값으로 저장
    max_dp[0] = copy.deepcopy(max_dp[1])
    min_dp[0] = copy.deepcopy(min_dp[1])
    
print(max(max_dp[0]), min(min_dp[0]))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] max_dp = new int[2][3];
		int[][] min_dp = new int[2][3];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < 3; i++) {
			max_dp[0][i] = Integer.parseInt(st.nextToken());
			min_dp[0][i] = max_dp[0][i];
		}
		
		// 입력할때 마다 dp 연산한다.
		int x1, x2, x3; // 입력 받을값 변수
		for(int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			x1 = Integer.parseInt(st.nextToken());
			x2 = Integer.parseInt(st.nextToken());
			x3 = Integer.parseInt(st.nextToken());
			// 최대값 dp 점화식
			max_dp[1][0] = x1 + Math.max(max_dp[0][0], max_dp[0][1]);
		    max_dp[1][1] = x2 + Math.max(max_dp[0][0], Math.max(max_dp[0][1], max_dp[0][2]));
		    max_dp[1][2] = x3 + Math.max(max_dp[0][1], max_dp[0][2]);
		    
		    // 최소값 dp 점화식
		    min_dp[1][0] = x1 + Math.min(min_dp[0][0], min_dp[0][1]);
		    min_dp[1][1] = x2 + Math.min(min_dp[0][0], Math.min(min_dp[0][1], min_dp[0][2]));
		    min_dp[1][2] = x3 + Math.min(min_dp[0][1], min_dp[0][2]);
		    
		    // 연산 끝난후에 이전값으로 저장
		    for(int k = 0; k < 3; k++) {
		    	max_dp[0][k] = max_dp[1][k];
		    	min_dp[0][k] = min_dp[1][k];
		    } 
		}
		
		System.out.println(Arrays.stream(max_dp[0]).max().getAsInt() + " " + Arrays.stream(min_dp[0]).min().getAsInt());
		
	}

}