백준 1749번 - 점수따먹기(java)

💡 문제 

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

 

개인적으로는 어려웠던 문제였는데 이게 골드4라니.. 충격적이다.

2가지 풀이를 하였는데, 둘 다 dp를 활용하고, dp에 약한 나는 다른 곳에서 아이디어를 얻어서 풀었다.

두 풀이 모두 점화식을 두 개 세워야 하는 문제였다 흑

 

1. 누적합 활용

2. 카데인 알고리즘 활용

 

💡 Sol 1.  누적합 활용

- 아이디어

이전에 풀었던 구간 합 구하기 5 문제의 2번 풀이를 활용하였다.

https://oha-study.tistory.com/20

백준 11660번 - 구간 합 구하기 5 (java)

 

1. (a,b) ~ (c,d) 누적합 구하기

이를 위해 (1,1) ~ (x,y) 합을 이용한다면 아래와 같이 식을 세울 수 있다. (큰 점화식)

 

2. (1,1) ~ (x,y) 합 구하기

 

DP 문제는 아래 3가지 단계로 이루어진다.

 

  1) dp 상태 배열 정의

• dp[x][y]는 (1,1) ~ (x,y) 사각형의 숫자의 합이다.

  2) 초기값 정의 

• 인덱스 0인 부분은 0으로 초기값 설정하기 위해 배열의 행과 열 크기를 +1 증가

  3) 점화식 세우기

• dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]

dp = new int[N + 1][M + 1];

 

 

3. (a,b) ~ (c,d) 누적합과 현재까지 구한 최댓값과 비교하여 갱신

 

 

- 코드

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

//sol 1. 누적합 활용
public class BOJ_G4_1749_점수따먹기 {
    public static int N, M;
    public static int map[][];
    public static int dp[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N + 1][M + 1];

        // 1. dp 상태 배열 정의 : (1,1)~(x,y) 사각형 숫자의 합
        // 2. 초기값 정의 : 인덱스 0인 부분은 0으로 초기화하기 위해 배열의 행과 열 크기를 +1
        dp = new int[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //------------ 입력 완료

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 3-2. 점화식 세우기
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + map[i][j];
            }
        }

        int answer = Integer.MIN_VALUE;
        for (int a = 1; a <= N; a++) {
            for (int b = 1; b <= M; b++) {
                for (int c = a; c <= N; c++) {
                    for (int d = b; d <= M; d++) {
                        // 3-1. 큰 점화식 세우기
                        int val = dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1];
                        if (val > answer) {
                            answer = val;
                        }
                    }
                }
            }
        }
        System.out.println(answer);
    }
}

 

💡 Sol 2.  카데인 알고리즘 활용

- 아이디어

이 풀이는 카데인 알고리즘을 알고 있는 경우 풀이할 수 있다.

아래 영상을 참고하여 문제를 해결하였다.

https://www.youtube.com/watch?v=yCQN096CwWM

 

1. 각 행의 특정 열의 구간의 합(열은 계속 이동)을 rowSum[] 이라는 배열에 저장한다.

2. rowSum 배열에서 카데인 알고리즘을 활용하여 가장 큰 합을 갖는 행의 구간을 찾는다.

 

- 코드

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

//sol 2. 카데인 알고리즘 활용
public class BOJ_G4_1749_점수따먹기_sol2 {
    public static int N, M;
    public static int map[][], sum[][];
    public static int rowSum[];
    public static int curSum, maxSum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        sum = new int[N][M]; //각 행의 처음부터 자신까지의 합
        rowSum = new int[N]; //현재 상태에서 각 행 별 합


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            sum[i][0] = map[i][0];
            for (int j = 1; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                sum[i][j] = sum[i][j - 1] + map[i][j];
            }
        }
        //------------ 입력 완료

        maxSum = Integer.MIN_VALUE;

        for (int L = 0; L < M; L++) { //왼쪽 열 이동
            for (int R = L; R < M; R++) { //오른쪽 열 이동
                for (int row = 0; row < N; row++) {
                    //rowSum 배열에 각 행의 L~R 열의 합을 저장
                    if (L == 0) {
                        rowSum[row] = sum[row][R];
                    } else {
                        rowSum[row] = sum[row][R] - sum[row][L - 1];
                    }
                }
                //카데인 알고리즘을 활용하여 가장 큰 합을 갖는 행의 범위를 찾음
                kadane();

                //최댓값과 비교
                if (curSum > maxSum) {
                    maxSum = curSum;
                }
            }
        }
        System.out.println(maxSum);
    }

    //rowSum의 부분배열 중 합이 가장 큰 값을 curSum에 저장 (카데인 알고리즘)
    private static void kadane() {

        // 1. dp 상태 배열 정의
        int[] subMaxSum = new int[N]; // 현재 인덱스까지의 부분배열 중 합이 가장 큰 값
        int[] mySum = new int[N]; // 현재 인덱스를 포함한 부분배열 중 합이 가장 큰 값

        // 2. 초기값 정의
        subMaxSum[0] = rowSum[0];
        mySum[0] = rowSum[0];

        for (int i = 1; i < N; i++) {
            // 3-2. 점화식
            mySum[i] = Integer.max(mySum[i - 1] + rowSum[i], rowSum[i]);
            // 3-1. 큰 점화식
            subMaxSum[i] = Integer.max(subMaxSum[i - 1], mySum[i]);
        }

        curSum = subMaxSum[N - 1];
    }
}