계산 로봇( BOJ 22342 )

문제 : https://www.acmicpc.net/problem/22342

22342번: 계산 로봇

 

문제 파악하기

문제를 이해하는데 가장 오랜 시간이 걸린 문제입니다. 설명이 조금은 난해하지만 차근차근 따라오면 문제는 쉽게 해결할 수 있습니다. 우선, 로봇에게는 3개의 값이 존재하는데 각각 입력값 / 저장값 / 출력값 이라고 부릅니다. 각각에 대해 하나씩 알아봅시다.

 

우선 입력값은 다른 로봇들의 출력값을 의미합니다. 다만, 모든 로봇이 아닌 특정 위치에 있는 로봇들의 출력값을 말합니다. 문제에서는 다음과 같은 설명으로 나타냈습니다.

 

좌표 (i, j)의 로봇의 입력 값은 |i−a| ≤ j −b, b < j인 모든 좌표 (a, b)에 있는 로봇들의 출력 값들이다.

 

현재 로봇을 기준으로 왼쪽에 있는 로봇들 중, 현재 로봇이 위치한 열과 떨어진 거리만큼 열의 범위가 늘어나는 범위 안에 있는 로봇들을 의미하며, 그림으로 표현하면 다음과 같이 나타낼 수 있습니다. 노란색으로 색칠한 범위가 (x, y) 위치에서 입력받는 로봇들의 범위입니다.

			(x, y)

 

저장값은 로봇이 입력받는 다른 로봇들의 출력값 중 가장 큰 값을 의미합니다. 그리고 출력값은 저장된 값에 자신의 초기 가중치를 더한 값을 의미합니다. 우리는 결국 로봇들의 입력을 분석하여 저장값을 구한 다음, 해당 로봇의 출력값을 구하면서 저장된 값 중 가장 큰 값을 찾아야 합니다.

 

문제는 단순해졌지만 시간복잡도 측면에서는 단순하지 않습니다. (x, y)의 입력 범위를 단순히 하나씩 확인하기에는 2초라는 시간은 턱없이 부족합니다. 따라서 우리는 (x, y) 왼쪽에 있는 로봇들의 도움을 받아야 합니다.

 

 

문제 해결하기

(x, y) 로봇의 저장값은 왼쪽에 있는 3개의 로봇만 확인하면 쉽게 구할 수 있습니다. 바로 (x-1, y-1), (x, y-1), (x+1, y-1) 로봇입니다. 로봇이 저장하는 값은 단순히 해당 입력 범위 내 가장 큰 값입니다. 따라서 얼마든 범위가 중복되어도 상관없으며, (x, y) 로봇의 범위는 단 3개의 로봇들의 입력으로 모두 처리할 수 있습니다.

		(x-1, y-1)
		(x, y-1)	(x, y)
		(x+1, y-1)

위의 표에서 볼 수 있듯이 (x-1, y-1), (x, y-1), (x+1, y-1)의 입력 범위를 모두 합치면 (x, y)의 입력 범위가 나옵니다. 따라서 (x, y)의 저장값은 다음과 같은 점화식으로 나타낼 수 있습니다.

 

(x, y) = max{ (x-1, y-1)의 출력값, (x, y-1)의 출력값, (x+1, y-1)의 출력값 }

 

따라서, 우리는 모든 (x, y)에 대해 위의 점화식을 사용해 저장값을 구한 다음, 가중치를 더해 출력값을 구합니다. 그리고 구한 출력값을 이용하여 이후 로봇의 저장값에 다시 활용하게 됩니다. 이렇게 탐색하면 제한 시간 안에 충분히 정답을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 2010
using namespace std;
 
int M, N;
int inp[NMAX][NMAX];
 
int ret;
int store[NMAX][NMAX], print[NMAX][NMAX];
 
int main() {
    // input
    scanf("%d %d", &M, &N);
    for(int i=1;i<=M;i++) {
        for(int j=1;j<=N;j++) {
            scanf("%1d", &inp[i][j]);
        }
    }
 
    // search
    for(int j=1;j<=N;j++) {
        for(int i=1;i<=M;i++) {
            
            // (i-1, j-1), (i, j-1), (i+1, j-1)값 비교
            for(int k=-1;k<=1;k++) store[i][j] = max( store[i][j], print[i+k][j-1] );
            print[i][j] = store[i][j] + inp[i][j];
 
            // 저장된 값 중 최댓값
            ret = max( ret, store[i][j] );
        }
    }
 
    // print
    printf("%d", ret);
}
 
/*
3 4
1234
2341
3412
ans: 11
*/

후기

문제를 이해하는데 가장 오랜 시간이 걸린 문제입니다. 입력 범위가 겹칠 수 있다는 사실을 간과한다면 나름 풀기 어려운 문제가 되지 않을까 생각합니다. 간단한 동적 프로그래밍 문제로, 동적 프로그래밍을 연습하는 사람에게 추천할만한 문제라고 생각합니다.