백준22342(계산 로봇)

계산 로봇

문제

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를 더한 값을 자신의 출력 값으로 한다.

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

 

입력

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

다음 M개의 줄에는 로봇들의 가중치들이 행 순서대로 주어진다. 각각의 줄은 한 행에 해당하며 N개의 숫자(한 자리 수)로 이루어진 문자열이 주어진다. 각 숫자는 격자 칸의 로봇의 가중치를 의미한다. 즉, 여기서 i번째 줄의 j번째 문자가 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	추가 제약 조건 없음.

---

실버 1인데 꽤나 고생했다.

핵심은 중복을 제거하면서 구하는것!

문제에서 피라미드 식으로 이전 열을 다구해야하는 것처럼 말을 하지만 사실 이전 열만 생각해주면 되는 방식이다.

그 이유는 그 3개의 칸에 현재 칸에서 구하려고하는 모든 범위를 커버하기 때문.

그렇게 때문에 그 3칸중 가장 큰값이 현재 칸의 가장 큰 입력값이 된다.

 

그리고 인덱스 에러때문에 어떻게 해야할까 고민하다가 너무 분기를 나누는거보다 그냥 패딩을 주는 방식으로 했다.

M = 1 일때 문제가 주로 발생하여 패딩을 주어서 인덱스 문제를 해결하였다.

그리고 계속 틀리길래 보니 시간 초과 python으로 푼 사람은 딱 1명 있었다.

그래서 pypy로 해결하였다.

'''
계산 로봇

'''
import sys
input = sys.stdin.readline

M, N = map(int,input().split())

D = [list(map(int,input().strip())) for _ in range(M)]

# 저장 패딩 두고 저장
save = [[0] * (N+2) for _ in range(M+2)]
output = [[0] * (N+2) for _ in range(M+2)]

# 초기화
for i in range(1,M+1):
    output[i][1] = D[i-1][0]

result = 0
# 열 순으로 탐색
for j in range(1,N+1):
    for i in range(1,M+1):
        # 3개 중 가장 큰 거
        save[i][j] = max(output[i-1][j-1],output[i][j-1],output[i+1][j-1])
        # 출력값 저장
        output[i][j] = save[i][j] + D[i-1][j-1]
        # 정답 갱신
        result = max(save[i][j],result)

print(result)