[백준/Java, Kotlin] 2096번 내려가기

 

 

문제 풀이(Java만 풀이)

이 문제는 dp로 풀어야한다.

처음에는 bfs로 풀었는데 메모리 초과가 떴다. bfs로 푼 코드는 아래 코드 부분에 남겨두겠어용.

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int N = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][3];

int[][] minArr = new int[N][3];
int[][] maxArr = new int[N][3];

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;

1. 문제에서 주어진 부분에 대해 입력을 받는다.

arr 배열을 만들었고, 최대 점수, 최소 점수를 각각 구해야하기 때문에 최대값들을 담을 maxArr 배열과 최소값들을 담을 minArr 배열을 생성했다.

max, min는 출력값을 담을 정수 변수이다.

 

for(int i=0; i<N; i++) {
    st = new StringTokenizer(bf.readLine());
    for(int j=0; j<3; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());

        if(i ==0) {
            maxArr[0][j] = arr[i][j];
            minArr[0][j] = arr[i][j];
        }
    }
}

2. 배열에 문제 주어진 값들을 입력 받는다.

이 때, maxArr와 minArr의 첫번째 행(0번 인덱스)에도 값을 담는다.

그럼 위와 같이 담긴다.

 

for(int n=1; n<N; n++) {
    //0열
    maxArr[n][0] = Math.max(maxArr[n-1][0], maxArr[n-1][1]) + arr[n][0];
    minArr[n][0] = Math.min(minArr[n-1][0], minArr[n-1][1]) + arr[n][0];

    //1열
    maxArr[n][1] = Math.max(maxArr[n-1][0], Math.max(maxArr[n-1][1], maxArr[n-1][2])) + arr[n][1];
    minArr[n][1] = Math.min(minArr[n-1][0], Math.min(minArr[n-1][1], minArr[n-1][2])) + arr[n][1];


    //2열
    maxArr[n][2] = Math.max(maxArr[n-1][2], maxArr[n-1][1]) + arr[n][2];
    minArr[n][2] = Math.min(minArr[n-1][2], minArr[n-1][1]) + arr[n][2];
}

3. 1번째 행부터 N-1번째 행까지 반복하면서 최대값, 최소값을 찾는다.

 

일단, 1번째 행이다.

arr[1][0] = 4부터 시작하고, arr[1][0]은 arr[0][0]=1과 arr[0][1]=2를 비교해서 더 큰 값을 maxArr[1][0]에 담고, 더 작은 값을 minArr[1][0]에 담는다. 이 때 arr[1][0] 값을 더해서 담아야한다.

 

그럼 위와같이 담기는 것을 볼 수 있다.

 

1번째 행의 1번째 열인 arr[1][1]은 0번째 행의 3개의 값과 비교해야한다. 왜냐하면 문제에서 " 바로 아래의 수, 붙어 있는 수로만 이동" 할 수 있다고 했기 때문 !

 

그럼 위와 같이 담긴다.

 

2번째 열은 0번째 열과 동일한 방법으로 2개만 비교하면 된다.

 

반복문을 다 돌게 되면 위와 같이 배열이 채워진다.

 

 

for(int i=0; i<3; i++) {
    max = Math.max(max, maxArr[N-1][i]);
    min = Math.min(min, minArr[N-1][i]);
}

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

4. 이제 마지막 행인 N-1 행을 반복하면서 최소값과 최대값을 구한 후 출력한다.

 

 

결론적으로

0열, 1열, 2열의 점화식은 각각

• 0열

maxArr[n][0] = Math.max(maxArr[n-1][0], maxArr[n-1][1]) + arr[n][0]

• 1열

maxArr[n][1] = Math.max(maxArr[n-1][0], Math.max(maxArr[n-1][1], maxArr[n-1][2]) + arr[n][1]

• 2열

maxArr[n][2] = Math.max(maxArr[n-1][1], maxArr[n-1][2]) + arr[n][2]

 

이다. (최소값도 동일)

 

코드

• Java 풀이(맞았습니다!) - 다이나믹 프로그래밍 ☺️

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][3];
		
		int[][] minArr = new int[N][3];
		int[][] maxArr = new int[N][3];
		
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;

		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0; j<3; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				
				if(i ==0) {
					maxArr[0][j] = arr[i][j];
					minArr[0][j] = arr[i][j];
				}
			}
		}
		
		for(int n=1; n<N; n++) {
			//0열
			maxArr[n][0] = Math.max(maxArr[n-1][0], maxArr[n-1][1]) + arr[n][0];
			minArr[n][0] = Math.min(minArr[n-1][0], minArr[n-1][1]) + arr[n][0];
			
			//1열
			maxArr[n][1] = Math.max(maxArr[n-1][0], Math.max(maxArr[n-1][1], maxArr[n-1][2])) + arr[n][1];
			minArr[n][1] = Math.min(minArr[n-1][0], Math.min(minArr[n-1][1], minArr[n-1][2])) + arr[n][1];
			
			
			//2열
			maxArr[n][2] = Math.max(maxArr[n-1][2], maxArr[n-1][1]) + arr[n][2];
			minArr[n][2] = Math.min(minArr[n-1][2], minArr[n-1][1]) + arr[n][2];
		}

		for(int i=0; i<3; i++) {
			max = Math.max(max, maxArr[N-1][i]);
			min = Math.min(min, minArr[N-1][i]);
		}
		
		System.out.println(max +" " + min);
		
	}
}

 

• Java 풀이 - BFS (메모리초과) 🥲

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

public class Main {
	static int N;
	static int[][] arr;
	static boolean[][] visited;
	
	static int[] dx = {1, 1, 1};
	static int[] dy = {-1, 0, 1};
	
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	
	public static class Node{
		private int x;
		private int y;
		private int cnt;
		private int sum;
		
		public Node(int x, int y, int cnt, int sum) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.sum = sum;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N][3];
		

		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0; j<3; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<3; i++) {
			visited = new boolean[N][3]; //방문배열 초기화
			bfs(i);
		}
		
		System.out.println(max + " " + min);
		
		
	}
	public static void bfs(int n) {
		Queue<Node> queue = new LinkedList<Node>();
		
		queue.add(new Node(0, n, 1, arr[0][n]));
		
		while(!queue.isEmpty()) {
			Node tmp = queue.poll();
			
			if(tmp.cnt == N) {
				max = Math.max(max, tmp.sum);
				min = Math.min(min, tmp.sum);
			}
			
			for(int d=0; d<3; d++) {
				int nx = dx[d] + tmp.x;
				int ny = dy[d] + tmp.y;
				
				if(nx<0 || nx>=N || ny<0 || ny>=3) continue;
				
				if(!visited[nx][ny]) {
					queue.add(new Node(nx, ny, tmp.cnt+1, tmp.sum + arr[nx][ny]));
				}
			}
		}
	}
}

 

• Kotlin 풀이 - 다이나믹 프로그래밍 ☺️

fun main(){
    var N = readln().toInt()

    var arr = Array(N){ IntArray(3) }
    var maxArr = Array(N){ IntArray(3) }
    var minArr = Array(N){ IntArray(3) }

    var max = Integer.MIN_VALUE
    var min = Integer.MAX_VALUE

    for(i in 0 until N){
        arr[i] = readln().split(" ").map{ it.toInt() }.toIntArray()
    }

    maxArr[0] = arr[0].clone()
    minArr[0] = arr[0].clone()

    for(n in 1 until N){
        //0열
        maxArr[n][0] = maxOf(maxArr[n-1][0], maxArr[n-1][1]) + arr[n][0]
        minArr[n][0] = minOf(minArr[n-1][0], minArr[n-1][1]) + arr[n][0]

        //1열
        maxArr[n][1] = maxOf(maxArr[n-1][0], maxOf(maxArr[n-1][1], maxArr[n-1][2])) + arr[n][1]
        minArr[n][1] = minOf(minArr[n-1][0], minOf(minArr[n-1][1], minArr[n-1][2])) + arr[n][1]

        //2열
        maxArr[n][2] = maxOf(maxArr[n-1][1], maxArr[n-1][2]) + arr[n][2]
        minArr[n][2] = minOf(minArr[n-1][1], minArr[n-1][2]) + arr[n][2]

    }

    for(i in 0 until 3){
        max = maxOf(max, maxArr[N-1][i])
        min = minOf(min, minArr[N-1][i])
    }
    println("$max $min")
}

 

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