PS/백준 [백준/2169] 로봇 조종하기 (Python) - Problem : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net Difficulty : Gold 2 Status : Solved Time : 00:28:30 문제 설명 더보기 NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오. 입력 및 출력 더보기 입력 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. 출력 첫째 줄에 최대 가치의 합을 출력한다. 입력 예시 5 5 10 25 7 8 13 68 24 -78 63 32 12 -69 100 -29 -25 -16 -22 -57 -33 99 7 -76 -11 77 15 출력 예시 319 풀이 DP 문제. 왼쪽 / 오른쪽 / 아래로 이동할 수 있어 언뜻 보면 어려워 보이지만, 한번 지나간 좌표는 다시 돌아갈 수 없다는 제약조건을 이해해보자. 즉 한 층에서는 왼쪽 / 오른쪽 일방통행만 가능하다. 따라서 왼쪽 방향으로 진행하는 Left Dp와, 오른쪽 방향으로 진행하는 Right Dp를 따로 구해볼 수 있다. 이 때, Left DP : L[0] = dp[i-1][0] + value[i][0], L[j] = max(L[j-1], dp[i-1][j]) + value[i][j] Right DP : R[M-1] = dp[i-1][M-1] + value[i][M-1], R[j] = max(R[j+1], dp[i-1][j]) + value[i][j] 가 성립한다! 최종적인 i행 j열의 DP값 dp[i][j] = max(L[j], R[j]) 이 성립하므로, O(NM)의 시간복잡도 내에 해결 가능하다. 풀이 코드 import sys input = sys.stdin.readline MAX = float('inf') N, M = map(int, input().split()) value_list = [list(map(int, input().split())) for _ in range(N)] dp = [[-MAX]*M for _ in range(N)] for i in range(M) : if i == 0 : dp[0][i] = value_list[0][i] else : dp[0][i] = dp[0][i-1] + value_list[0][i] for i in range(1, N) : Ldp, Rdp = [-MAX]*M, [-MAX]*M Ldp[0] = dp[i-1][0] + value_list[i][0] Rdp[-1] = dp[i-1][-1] + value_list[i][-1] for j in range(1, M) : Ldp[j] = max(Ldp[j-1], dp[i-1][j]) + value_list[i][j] Rdp[-1-j] = max(Rdp[-j], dp[i-1][-1-j]) + value_list[i][-1-j] for j in range(M) : dp[i][j] = max(Ldp[j], Rdp[j]) print(dp[-1][-1]) 풀이 완료 공유하기 URL 복사카카오톡 공유페이스북 공유엑스 공유 게시글 관리 구독하기마젠티노's 저작자표시 비영리 동일조건 Contents 당신이 좋아할만한 콘텐츠 [백준/1219] 오민식의 고민 (Python) 2023.09.12 [백준/1306] 달려라 홍준 (Python) 2023.09.12 [백준/1111] IQ Test (Python) 2023.09.09 [백준/1175] 배달 (Python) 2023.09.08 댓글 0 + 이전 댓글 더보기