백준(BOJ) 22342 - 계산로봇

DP 문제였다.

생각보다 해당 셀의 저장값을 O(1) 시간만에 구하는것이 어려워보였다.

다만 그림을 그려보며 패턴을 파악하면 쉽게 알 수 있는 문제였다.

 

 

주요하게 필요한 것

1. 각 셀의 저장값을 알아낸다.

2. 알아낸 저장값을 이용해 최댓값을 갱신한다.

3. 저장값에 가중치를 더해 출력값을 구하고, 배열에 저장한다.

문제를 3단계의 과정으로 풀어낼 수 있다.

다만, 문제의 조건을 보면 N과 M의 범위가 1 <= N, M <= 2000이므로, O(NM)시간만에 구해야 시간복잡도가 가능한 문제였다.

(NM -> 4,000,000)

여기서 각 셀의 저장값을 알아내야 하므로 각 셀을 한 번씩 방문하는것은 필수적인 일이다. 여기서 O(NM)이 소요되게 된다.

따라서 저장값을 O(1)만에 구해야 풀이 할 수 있는 문제였다.

 

---

저장값을 O(1)만에 구하는 법

나이브하게 생각해보자. 문제에 나와있듯이 한 셀의 저장값을 구하려면, 입력값들 중 가장 큰 값을 찾아야 한다.

입력값들을 탐색하기 위해 나의 이전 열에 있는 셀들을 피라미드 형태로 모두 방문한다면, 최악이라고 가정 했을 때 한 셀의 저장값을 구하기 위해 모든 셀의 절반을 탐색해야 한다. 이렇게는 O(1)만에 구할 수 없다.

 

O(1)만에 저장값을 구하기 위해서는, 총 3칸의 셀을 탐색해야 한다.

i,j셀의 저장값을 구한다고 했을 때

i - 1, j - 1

i, j - 1

i + 1, j - 1

총 3칸이다.

i,j셀의 입력값에 포함되는 셀들은 피라미드 형태로 좌측으로 뻗어나가는데, 해당 3셀이 모든 피라미드 영역을 커버하며 최댓값을 구하기 때문이다.

 

---

 

제출 코드

package src;

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

public class BACK_22342 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] d = new int[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                d[i][j] = line.charAt(j) - '0';
            }
        }
        int maxSave = 0;
        int[][] output = new int[N][M];
        for (int col = 0; col < M; col++) {
            for (int row = 0; row < N; row++) {
                int subMax = 0;
                if (col == 0) output[row][col] = d[row][col];
                else {
                    if (row - 1 >= 0) subMax = Math.max(subMax, output[row - 1][col - 1]);
                    subMax = Math.max(output[row][col - 1], subMax);
                    if (row + 1 < N) subMax = Math.max(subMax, output[row + 1][col - 1]);
                    maxSave = Math.max(subMax, maxSave);
                    output[row][col] = subMax + d[row][col];
                }
            }
        }
        System.out.println(maxSave);
    }
}

 

---

 

마무리

DP 문제들은 점화식만 구하면 쉽게 풀 수 있지만, 그 식까지 가는 과정이 쉽지 않은 편이다.