KOI 2차 2021 초2/중1- 계산 로봇 > 문제은행 : 정보올림피아드&알고리즘


4797 : 계산 로봇

제한시간
2000 ms   
메모리제한
1024 MB   
해결횟수
29 회   
시도횟수
61 회   

문제

  M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다.

 

 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고,
각 열에는 왼쪽에서부터 오른쪽으로 1부터 N까지의 번호가 붙어 있다.
이를 통해 격자 칸의 위치를 (행 번호, 열 번호)의 좌표로 표시할 수 있다.

 

 각 로봇은 하나 이상의 입력 값, 하나의 저장 값, 하나의 출력 값을 가진다.

 

 로봇들은 제일 왼쪽 열의 로봇들부터 열 번호 순서대로 동작한다. 같은 열에 있는 로봇들은 동시에 동작한다.

 

 로봇들의 동작은 다음과 같다. (표현 |A|는 정수 A의 절댓값을 의미한다. 즉, A ≥ 0인 경우 |A| = A, A < 0 인 경우 |A| = −A.)

 

 • 제일 왼쪽 열에 있는 로봇의 입력 값은 0 하나로 정한다.

 • 좌표 (i, j)의 로봇의 입력 값은 |i−a| ≤ j −b, b < j인 모든 좌표 (a, b)에 있는 로봇들의 출력 값들이다.
   (아래 그림에서 별로 표시된 칸의 로봇의 입력 값들은 왼쪽 회색 칸들의 로봇들의 출력 값들이다.)

 


 

 • 각 로봇은 자신의 입력 값들 중 최댓값을 자신의 저장 값으로 한다.

 • 각 로봇은 자신의 저장 값에 자신의 가중치 Di,j를 더한 값을 자신의 출력 값으로 한다.

 

 로봇들의 가중치를 입력받아 로봇들의 저장 값최댓값(가장 큰 값)을 계산하는 프로그램을 작성하라.

 

제약 조건

• 1 ≤ M ≤ 2 000

• 1 ≤ N ≤ 2 000.

• 모든 i, j (1 ≤ i ≤ M, 1 ≤ j ≤ N)에 대해, 1 ≤ Di,j ≤ 9.

 

부분문제

1. (3점) N = 1.

2. (8점) N = 2.

3. (9점) M = 1.

4. (21점) M ≤ 100, N ≤ 100.

5. (59점) 추가 제약 조건 없음.​ 


입력형식

 첫 번째 줄에 두 정수 M과 N이 공백 하나를 사이로 두고 주어진다.

 

 다음 M개의 줄에는 로봇들의 가중치들이 행 순서대로 주어진다.
각각의 줄은 한 행에 해당하며 N개의 숫자(한 자리 수)로 이루어진 문자열이 주어진다.
각 숫자는 격자 칸의 로봇의 가중치를 의미한다. 즉, 여기서 i번째 줄의 j번째 문자가 Di,j이다.​


출력형식

첫 번째 줄에 로봇들의 저장 값 중 최댓값을 출력한다. 


입력 예

3 4
1234
2341
3412

출력 예

11


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP