[백준, Java] 24427번, 알고리즘 수업 - 행렬 경로 문제 4, (DP)

문제 링크

24427번: 알고리즘 수업 - 행렬 경로 문제 4

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 행렬의 위치에서 오른쪽, 아래 방향으로만 이동이 가능합니다.

2. (1, 1) → (n, n)까지 도착할 때 P개의 중간 원소를 반드시 1개 이상 거쳐야 합니다.

3. (n, n)까지 도착하는 경로 중 가장 높은 점수를 결과로 출력합니다.

4. 점수는 해당 경로에 존재하는 원소들의 합입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 점화식을 통한 (n, n)까지 최대 점수를 탐색합니다.

 

3. 탐색을 통해 얻은 최대 점수를 결과로 출력합니다.

 

 

배열 이동하기(DP)

 

문제에서 설명하는 점화식을 살펴보겠습니다

 

 

[점화식] 

 

DP[i][j] = Math.max(DP[i-1][j], DP[i][j-1]) + [i][j] 위치의 점수

 

위 점화식을 그대로 사용하면, 각 위치에서 얻을 수 있는 최대 점수를 얻을 수 있습니다.

 

여기서 이 문제의 핵심은 P개의 위치를 최소 1번은 방문해야 한다는 것입니다.

 

즉, 현재 위치의 최대 점수(DP[i][j])가 방문한 점수이면 유효하지만, 방문하지 않았으면 유효하지 않은 점수입니다.

 

P개의 장소는 항상 1번 이상 방문하기 때문에 유효한 점수로 표현할 수 있습니다.

 

유효한 점수가 아니면, 해당 점수는 최고 점수가 될 수 없기 때문에 최대 점수를 다시 탐색합니다.

 

[유효한 점수일 때 최대 점수 점화식]

 

 

DP[i-1][j]만 유효할 때

 

DP[i][j] = DP[i-1][j] + [i][j] 위치의 점수

 

DP[i][j-1]만 유효할 때

 

DP[i][j-1] = DP[i][j-1] + [i][j] 위치의 점수

 

DP[i][j-1], DP[i-1][j] 모두 유효할 때

 

DP[i][j] =  Math.max(DP[i-1][j], DP[i][j-1]) + [i][j] 위치의 점수

 

 

※ DP[i-1][j], DP[i][j-1]이 하나라도 유효하면 DP[i][j]는 유효한 최대 점수가 됩니다.

 

[i][j]의 위치가 유효한지 확인하는 것은 boolean[][]을 이용하여 확인하였습니다.

 

 

결과적으로 DP[N][N]의 최대 점수를 결과로 출력합니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 5

 

P = 4(빨간색 표시)

 

1	1	1	1	7
1	1	1	3	1
1	2	1	1	1
1	1	2	1	1
1	1	1	1	1

 

 

2. 점화식을 통한 (n, n)까지 최대 점수를 탐색합니다.

 

DP[i][j] : (i, j)위치에 있을 때 얻을 수 있는 최대 점수

 

최대 점수를 구하는 점화식 진행

 

 

1	2	3	4	11
2	3	4	7	12
3	5	6	8	13
4	6	8	9	14
5	7	9	10	15

 

 

P개의 위치는 유효한 점수로 표현합니다.

 

		4
	5
4		8

 

 

유효한 최대 점수 기준 점화식 진행

 

0	0	0	0	0
0	0	4	7	8
0	5	6	7	8
4	6	8	9	10
5	7	8	10	11

 

3. 탐색을 통해 얻은 최대 점수를 결과로 출력합니다.

 

[N][N]으로 도착하는 최대 점수는 DP[N][N] : 11

 

11 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 입력되는 배열의 정보를 띄어쓰기 기준 나누었습니다.
• 최대 점수 기준 점화식으로 DP1[][]에 저장하였습니다.
• P개의 유효한 위치 기준 유효한 최대 점수 기준 점화식으로 DP2[][]에 저장합니다.
• (N, N) 최대 점수인 DP2[N][N]을 BufferdWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N+1][N+1];
        //입력 값 저장
        for(int i=1;i<=N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //DP[i][j] : 최대 점수 기준 점화식 진행
        int[][] DP1 = new int[N+1][N+1];
        for(int i=1;i<=N;i++) {
            for (int j = 1; j <= N; j++) {
                DP1[i][j] = Math.max(DP1[i - 1][j], DP1[i][j - 1]) + arr[i][j];
            }
        }
        //DP[i][j] : 유효한 최대 점수 기준 점화식 진행
        int[][] DP2 = new int[N+1][N+1];
        boolean[][] visitedCheck = new boolean[N+1][N+1];
        int M = Integer.parseInt(br.readLine());
        //P개의 유효한 위치 저장
        for(int i=1;i<=M;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            visitedCheck[r][c] = true;
            DP2[r][c] = DP1[r][c];
        }
        //점화식 진행
        for(int i=1;i<=N;i++) {
            for (int j = 1; j <= N; j++) {
                if (visitedCheck[i - 1][j]) {
                    DP2[i][j] = Math.max(DP2[i][j], DP2[i - 1][j] + arr[i][j]);
                    visitedCheck[i][j] = true;
                }
                if (visitedCheck[i][j - 1]) {
                    DP2[i][j] = Math.max(DP2[i][j], DP2[i][j - 1] + arr[i][j]);
                    visitedCheck[i][j] = true;
                }
            }
        }
        //[N][N]의 최대 점수 BufferedWriter 저장
        bw.write(String.valueOf(DP2[N][N]));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}