백준 22342. 계산 로봇

tose33 2022. 9. 5. 14:20

22342번: 계산 로봇

M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의

www.acmicpc.net

dp 문제.

d[i][j] : [i][j]의 출력값

이 문제는 결과적으로 보면 모든 위치를 탐색하는데 현재 위치가 [r][c] 라면 [r-1][c-1], [r][c-1], [r+1][c-1] 세 위치 중 가장 큰 값이 d[r][c]가 된다.

즉 점화식은 d[r][c] = max(d[r-1][c-1], d[r][c-1], d[r+1][c-1])이 된다.

각 로봇은 입력값들 중 최댓값을 저장값으로 하기 때문에 d[r][c] 기준 [r-1][c-1], [r][c-1], [r+1][c-1] 값들이 [r][c]의 입력값이 되고 그중 가장 큰 값이 출력값이 된다.