[JAVA] 2096번 - 내려가기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

어제 풀었던 문제와 거의 동일하다. 다만 최대값과 최소값을 모두 구해야하니까 최대값을 구하는 DP배열하나, 최소값을 구하는 DP배열 각각 만들어서 구하면 된다!!

 

또한 이 문제가 DP인 이유는 얻을 수 있는 최대점수, 최소점수를 구해야하기 때문이다 

해당 칸의 점수를 더할 때, 이전 칸의 점수들 중에서 큰 값을 선택해서 더해야한다.

현재 상태의 값을 구할때, 이전 칸의 상태를 활용해야 하기 때문에 DP문제이다. 

그리고 구해진 값들을 메모이제이션에 의해 DP배열에 저장해놓으면 이전의 값들을 활용할때

다시 호출해서 시간이 낭비되는 일이 생기지 않는다.

 

0열, 1열, 2열이 있으면

0열의 경우는 0열, 1열에서 큰 값이 선택되어야 한다.

1열의 경우는 0열, 1열, 2열에서 큰 값이 선택되어야 한다.

2열의 경우는 1열, 2열에서 큰 값이 선택되어야 한다.

 

이것을 점화식으로 나타내면 다음과 같다.

max_dp[i][0] = Math.max(max_dp[i-1][0], max_dp[i-1][1])+ arr[i][0];
max_dp[i][1] = Math.max(max_dp[i-1][0], Math.max(max_dp[i-1][1], max_dp[i-1][2]))+arr[i][1];
max_dp[i][2] = Math.max(max_dp[i-1][2], max_dp[i-1][1])+arr[i][2];

 

나는 행은 1부터 시작하도록 코드를 짰다.

i-1에서 인덱스 에러가 날 수 있기 때문이다.

1부터 시작하면 가장 작은 문제의 답을 미리 초기화하지 않아도 되기 때문이다. 

 

for문을 한번만 쓰면서 각 한줄을 입력받을 때 각 0열, 1열, 2열에 들어갈 숫자들을 a,b,c라는 변수에 할당을하고 바로 최대dp와 최소dp를 구했다.

 

 

시간복잡도

O(N)이다.N은 최대100,000이니까 시간내에 충분히 가능하다

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 입력을 받는다

2. 변수들을 a,b,c에 할당해서 바로 최대,최소 dp를 구한다

3. 출력 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

바로 성공

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

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[n+1][3];
        int min_dp[][] = new int[n+1][3];
        
        
        StringTokenizer st;
        for(int i=1; i<=n; i++) {
           st = new StringTokenizer(br.readLine());
           
           int a = Integer.parseInt(st.nextToken());
           int b = Integer.parseInt(st.nextToken());
           int c = Integer.parseInt(st.nextToken());
           
           //최대값 구하기 
           max_dp[i][0] = Math.max(max_dp[i-1][0], max_dp[i-1][1])+a;
           max_dp[i][1] = Math.max(max_dp[i-1][0], Math.max(max_dp[i-1][1], max_dp[i-1][2]))+b;
           max_dp[i][2] = Math.max(max_dp[i-1][2], max_dp[i-1][1])+c;
           
           //최소값 구하기 
           min_dp[i][0] = Math.min(min_dp[i-1][0], min_dp[i-1][1])+a;
           min_dp[i][1] = Math.min(min_dp[i-1][0], Math.min(min_dp[i-1][1], min_dp[i-1][2]))+b;
           min_dp[i][2] = Math.min(min_dp[i-1][2], min_dp[i-1][1])+c;
        }
        
        int maxx = Math.max(max_dp[n][0], Math.max(max_dp[n][1], max_dp[n][2]));
        int minn = Math.min(min_dp[n][0], Math.min(min_dp[n][1], min_dp[n][2]));
        System.out.println(maxx + " "+ minn);
    }   
}