[백준]2096번 내려가기

ynoolee·2021년 8월 23일
0

코테준비

목록 보기
29/146

2096번: 내려가기
(소요시간 : 48분..)

  • 처음 숫자 선택 : 3개의 숫자 중 하나를 고른다.
  • 첫 줄 → 마지막 줄 까면 끝나는 놀이
  • 다음 줄로 넘어 갈 때의 제약 조건
    • 바로 아래칸 OR "바로 아래칸에 인접한 칸으로만 "
    • 근데 각 줄 당 세개의 칸 만 존재.
  • 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하라.
  • 점수 = 원룡이가 위치한 곳의 수의 합
  • 조건
    • N개의 줄, N은 1이상 10만 이하.
    • 각 숫자는 0~9 의 정수

풀이 생각 : 첫 번째로 떠오르는 것은 DP

  • 왜냐하면, 첫 번 째 줄의 숫자도, 무작정 가장 큰 수나, 가장 작은 수를 선택하면 안된다.
1 2 3 -> 3을 선택
4 0 1 -> 4를 선택할 수가 없다. 또 이 줄의 max인 1선택하면
9 6 1 -> 여기서 또, 9를 선택할 수가 없다. 
0 7 8
하나의 선택은 어느 range까지에서의 min, max에 영향? -> 한 줄 
// 정답 22 7
  • 각 줄에서는 index 0,1,2에 있는 것 중 하나를 선택하도록 한다.

  • 현재 줄의 index에 +1,0,-1을 선택 할 수 있으며 → 이것이 0보다 작거나 2보다 크면 out of range 이므로 pass한다.

  • 전체탐색처럼 생각해 보면, 결국 중복되는 subproblem들이 존재 한다.

    이 경우, 
    첫 줄에서 1을 선택할 때, 두 번째 줄에서 4,0 선택 가능
    첫 줄에서 2를 선택할 때, 두 번째 줄에서 4,0,1 선택가능.
    결국 다음 줄에서 선택한 것은 그 다음줄에만 영향을 주니
    subproblem이 생긴다. 
    이를 top down 방식으로 생각하되, 이미 방문한 것을
    재방문 하지 않도록만 해 보자. 
    1 2 3
    4 0 1
    9 6 
  • min 과 max 에 대한 것을 따로 해야하기 때문에, cache는 3차원으로 생성하였다.

  • 이미 해당 좌표에 대한 min 을 구하기 위한 여정을 떠났다면( min을 구하기 위한 과정에서 해당 좌표를 이미 방문) 다시 방문 할 필요가 없다.

  • 이미 해당 좌표에 대한 max 를 구하기 위한 여정을 떠났다면( min을 구하기 위한 과정에서 해당 좌표를 이미 방문) 다시 방문 할 필요가 없다.

  • 재귀함수를 사용하는 방식의 DP는 잘 생각나는데, 그 외의 것을 계속해서 못 해내고 있다.. 그래서 bottom up 방식으로도 다시 하나 짜 보았다.

top down approach

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 int n;
    public static int[][] board = new int[100000][3];
    public static int[][][] cache = new int[100000][3][2];
    public static boolean[][][] visit = new boolean[100000][3][2];
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int c=0;c<3;c++){
                board[i][c] = Integer.parseInt(st.nextToken());
            }
        }
        // setting cache
        for(int r=0;r<n;r++){
            for(int c=0;c<3;c++)
                Arrays.fill(cache[r][c],-1);
        }
    }
    // max 에 대해, min 에 대해 각각 해도 될 것 같다.
    // max는 cahce[r][c]의 0에 , min 은 1에 저장
    // target은 지금 구하는게 max인지 min인지를 나타낸다.
    public static int dp_max(int y,int x){
        if(y==n-1) return board[y][x];
        if(cache[y][x][0]!=-1)return cache[y][x][0];
        int ny=y+1,nx=0,max=0;
        for(int idx=-1;idx<2;idx++){
            // curx + idx
            nx = x +idx;
            if(nx<0||nx>2) continue;
            max = Math.max(max,dp_max(ny,nx));
        }
        max += board[y][x];
        return cache[y][x][0]=max;
    }
    public static int dp_min(int y, int x){
        if(y == n-1) return board[y][x];
        if(cache[y][x][1]!=-1) return cache[y][x][1];
        int ny =y+1,nx=0,min = Integer.MAX_VALUE; // 9 * 100000 = 90만
        for(int idx=-1;idx<2;idx++){
            nx = x +idx;
            if(nx<0 || nx>2) continue;
            min = Math.min(min,dp_min(ny,nx));
        }
        min += board[y][x];
        return cache[y][x][1]=min;
    }
    public static void main(String[] args) throws IOException {
        Setting();
        int max=0,min=Integer.MAX_VALUE;
        for(int idx=0;idx<3;idx++){
            min = Math.min(min,dp_min(0,idx));
            max = Math.max(max,dp_max(0,idx));
        }
        System.out.println(max+" "+min);
    }
}

bottom up 방식

  • for문을 사용한다.

  • 공간 복잡도를 최소화 하기 위하여, cache 배열을 사용하지 않고, min, max 변수를 for문을 도는 동안 update하는 방식을 사용할 수 있다.

    • -> 각 column에 대한 min, max를 각 row를 진행해 나가면서 update 해 나가야 한다.
    • update란 자고로.. for문을 반복하며 현재값이 이전값이 되므로, int[3][2] 짜리의 min, max 배열을 사용한다.
  • r행 c열 에 대해 구할 때, r-1행 c-1열 , r-1행 c열, r-1행 c+1열 에 더하는 것 중 가장 max값 , 또는 min 을 update한다.

package coding;

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

public class Main {
    public static int n;
    public static int[][] board = new int[100000][3];
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int c=0;c<3;c++){
                board[i][c] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Setting();
        bottomUp();

    }
    private static void bottomUp() {
        // 마지막에 이 셋 중 max  -> real max
        // 마지막에 이 셋 중 min -> real min
        // mins[r][0] 은 pre (이전 row)
        // mins[r][1] 은 cur (현재 row) 
        int[][] mins = new int[2][3];
        int[][] maxs = new int[2][3];
        // INIT
        for(int c=0;c<3;c++) {
            mins[0][c] = board[0][c];
            maxs[0][c] = board[0][c];
        }
        // SOLVE
        for(int row=1;row<n;row++){
            // mins,max[0]을 구하기 위해서는  -> c와 c+1을
            mins[1][0] = Math.min(mins[0][0],mins[0][1])+board[row][0];
            maxs[1][0] = Math.max(maxs[0][0],maxs[0][1])+board[row][0];

            // mins,max[1]을 구하기 위해서는 -> c-1과 c와 c+1을
            mins[1][1] = Math.min(mins[0][0],mins[0][1]);
            mins[1][1] = Math.min(mins[1][1],mins[0][2]) + board[row][1];
            maxs[1][1] = Math.max(maxs[0][0],maxs[0][1]);
            maxs[1][1] = Math.max(maxs[1][1],maxs[0][2]) + board[row][1];
            // mins,max[2]를 구하기 위해서는 -> c-1과 c를
            mins[1][2] = Math.min(mins[0][1],mins[0][2]) + board[row][2];
            maxs[1][2] = Math.max(maxs[0][1],maxs[0][2]) + board[row][2];
            // 다시 pre와 cur을 바꾼다.
            for(int c=0;c<3;c++){
                mins[0][c]=mins[1][c];
                maxs[0][c]=maxs[1][c];
            }
        }
        // 셋 중 최대 최소 값을 구한다.
        int resmax=0,resmin = Integer.MAX_VALUE;
        for(int c=0;c<3;c++){
            resmax = Math.max(resmax,maxs[0][c]);
            resmin = Math.min(resmin,mins[0][c]);
        }
        System.out.println(resmax+" "+resmin);
    }
}

0개의 댓글