[JAVA] 백준 2096 - 내려가기

https://www.acmicpc.net/problem/2096

 

 

 

맨 처음 풀었을떄 코드 :  bfs -> 메모리초과

import org.w3c.dom.Node;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static int N;
    public static int[][] map;
    public static int max = Integer.MIN_VALUE;
    public static int min = Integer.MAX_VALUE;
    public static Queue<Point> queue = new LinkedList<>();
    public static int[][] marked;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][3];
        marked = new int[N][3];
        for(int i = 0 ; i < N ; i++){
            String[] line = br.readLine().split(" ");
            map[i][0] = Integer.parseInt(line[0]);
            map[i][1] = Integer.parseInt(line[1]);
            map[i][2] = Integer.parseInt(line[2]);
            marked[i][0] = -1;
            marked[i][1] = -1;
            marked[i][2] = -1;
        }
        queue.add(new Point(0,0,map[0][0]));
        queue.add(new Point(0,1,map[0][1]));
        queue.add(new Point(0,2,map[0][2]));

        while(!queue.isEmpty()){
            Point p = queue.poll();
//            System.out.println("queue : " + queue);
            if(marked[p.x][p.y] == -1) marked[p.x][p.y] = p.score;
            ArrayList<Point> candidates = new ArrayList<>();
            if(p.x == N - 1){ // 도착
                max = Integer.max(max, p.score);
            }else if(p.y == 0){
                candidates.add(new Point(p.x + 1 , 0 , p.score + map[p.x + 1][0]));
                candidates.add(new Point(p.x + 1 , 1 , p.score + map[p.x + 1][1]));

            }else if(p.y == 1){
                candidates.add(new Point(p.x + 1 , 0 , p.score + map[p.x + 1][0]));
                candidates.add(new Point(p.x + 1 , 1 , p.score + map[p.x + 1][1]));
                candidates.add(new Point(p.x + 1 , 2 , p.score + map[p.x + 1][2]));

            }else {
                candidates.add(new Point(p.x + 1 , 1 , p.score + map[p.x + 1][1]));
                candidates.add(new Point(p.x + 1 , 2 , p.score + map[p.x + 1][2]));
            }

            for(Point candidate : candidates){
                if(marked[candidate.x][candidate.y] == -1 || marked[candidate.x][candidate.y] < candidate.score){
                    queue.add(candidate);
                }
            }




        }

        for(int i = 0 ; i < N ; i++){
            marked[i][0] = -1;
            marked[i][1] = -1;
            marked[i][2] = -1;
        }
        queue.add(new Point(0,0,map[0][0]));
        queue.add(new Point(0,1,map[0][1]));
        queue.add(new Point(0,2,map[0][2]));

        while(!queue.isEmpty()){
            Point p = queue.poll();
//            System.out.println("queue : " + queue);
            if(marked[p.x][p.y] == -1) marked[p.x][p.y] = p.score;
            ArrayList<Point> candidates = new ArrayList<>();
            if(p.x == N - 1){ // 도착
                min = Integer.min(min, p.score);
            }else if(p.y == 0){
                candidates.add(new Point(p.x + 1 , 0 , p.score + map[p.x + 1][0]));
                candidates.add(new Point(p.x + 1 , 1 , p.score + map[p.x + 1][1]));

            }else if(p.y == 1){
                candidates.add(new Point(p.x + 1 , 0 , p.score + map[p.x + 1][0]));
                candidates.add(new Point(p.x + 1 , 1 , p.score + map[p.x + 1][1]));
                candidates.add(new Point(p.x + 1 , 2 , p.score + map[p.x + 1][2]));

            }else {
                candidates.add(new Point(p.x + 1 , 1 , p.score + map[p.x + 1][1]));
                candidates.add(new Point(p.x + 1 , 2 , p.score + map[p.x + 1][2]));
            }

            for(Point candidate : candidates){
                if(marked[candidate.x][candidate.y] == -1 || marked[candidate.x][candidate.y] > candidate.score){
                    queue.add(candidate);
                }
            }




        }

        System.out.println(max + " " +  min);
    }


}

class Point {
    int x;
    int y;
    int score;

    public Point(int x , int y, int score){
        this.x = x;
        this.y = y;
        this.score = score;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
    @Override
    public String toString(){
        return "[" +x + "," + y + ","  +  score + "]";
    }
}

 

 

 

 

dp_max[2][3]와 dp_min[2][3]을 선언하고

세칸각각 dp를 수행한다. 

import org.w3c.dom.Node;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static int N;
    public static int[][] dp_max = new int[2][3];
    public static int[][] dp_min = new int[2][3];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for(int i = 0 ; i < N ; i++){
            String[] line = br.readLine().split(" ");
            int _1 = Integer.parseInt(line[0]);
            int _2 = Integer.parseInt(line[1]);
            int _3 = Integer.parseInt(line[2]);

            if(i == 0) {
                dp_max[i % 2][0] = _1;
                dp_min[i % 2][0] = _1;
                dp_max[i % 2][1] = _2;
                dp_min[i % 2][1] = _2;
                dp_max[i % 2][2] = _3;
                dp_min[i % 2][2] = _3;
            } else {
                dp_max[i % 2][0] = Integer.max(dp_max[(i -1) % 2][0], dp_max[(i -1) % 2][1]) + _1;
                dp_max[i % 2][1] = Integer.max(Integer.max(dp_max[(i -1) % 2][0], dp_max[(i -1) % 2][1]), dp_max[(i -1) % 2][2]) + _2;
                dp_max[i % 2][2] = Integer.max(dp_max[(i -1) % 2][1], dp_max[(i -1) % 2][2]) + _3;

                dp_min[i % 2][0] = Integer.min(dp_min[(i -1) % 2][0], dp_min[(i -1) % 2][1]) + _1;
                dp_min[i % 2][1] = Integer.min(Integer.min(dp_min[(i -1) % 2][0], dp_min[(i -1) % 2][1]), dp_min[(i -1) % 2][2]) + _2;
                dp_min[i % 2][2] = Integer.min(dp_min[(i -1) % 2][1], dp_min[(i -1) % 2][2]) + _3;
            }

            max = Integer.max(Integer.max(dp_max[i % 2][0],dp_max[i % 2][1]),dp_max[i % 2][2]);
            min = Integer.min(Integer.min(dp_min[i % 2][0],dp_min[i % 2][1]),dp_min[i % 2][2]);
        }
        System.out.println(max + " " + min);
    }


}