https://www.acmicpc.net/problem/14430
난이도 : S2
Tag : DP
풀이 일자 : 2025-03-08
문제 탐색하기
N: 탐사할 영역의 세로길이 (1 <=N <=300)
M: 탐사할 영역의 가로길이 (1 <=M <=300)
1: 자원
0: 빈 땅
로봇은 왼쪽 위(1, 1)부터 오른쪽 아래(N, M)까지 자원을 채집
이동 가능 방향: 오른쪽 또는 아래쪽
즉, N*M의 땅에서 로봇이 이동하며 모을 수 있는 자원의 최대 개수를 구하면 됩니다.
가능한 시간복잡도
완전탐색:
각 위치에서 왼쪽 또는 오른쪽으로 이동 가능하므로 대략 O(2^(N*M))입니다.
최대 시간복잡도를 생각하면 O(2^(300*300))이므로 탐색 불가능합니다.
DP:
각 위치에 왔을 때 최선의 값을 유지하며 이동시 시간복잡도가 O(N*M)입니다.
N*M ≤ 90,000이므로 충분히 문제를 해결 가능합니다.
알고리즘 선택
DP를 선택해 보겠습니다.
문제를 보면 모든 영역에서 오른쪽, 또는 아래로만 이동합니다.
그러므로 dp [y][x]를 해당 위치까지 도달했을 때 모을 수 있는 자원의 최대 개수로 정의합니다.
(y, x)에 도착하기 전에 가능한 경로는 두 가지입니다.
- 위쪽에서 내려오는 경우 → dp[y-1][x]
- 왼쪽에서 오는 경우 → dp[y][x-1]
따라서, 둘 중 더 많은 자원을 모은 경로를 선택하면 됩니다.
그렇다면 아래와 같은 점화식을 도출할 수 있습니다.
dp[y][x] = land[y][x] + Math.max(dp[y-1][x], dp[y][x-1])
기저사례
첫 번째 행과 첫 번째 열은 오직 한 방향으로만 이동 가능하므로, 아래와 같이 초기화합니다.
- 첫 번째 열 (dp[y][0])
- 위쪽에서만 내려올 수 있음
- dp[y][0] = dp[y-1][0] + land[y][0]
- 첫 번째 행 (dp[0][x])
- 왼쪽에서만 이동 가능
- dp[0][x] = dp[0][x-1] + land[0][x]
왜냐하면 위 두 경우는 계속 아래로 끝까지, 오른쪽으로 끝까지 이동하는 경우만 존재하기 때문입니다.
아래 예제를 예시로 든다면 :
5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0
dp[0][0] = 0 dp[0][1] = 1 dp[0][2] = 1 dp[0][3] = 1
dp[1][0] = 0
dp[2][0] = 1
dp[3][0] = 2
dp[4][0] = 3 로 세팅이 됩니다.
코드 설계하기
- N, M 크기의 땅 정보를 입력받고, land[][] 배열을 초기화합니다.
- 첫 번째 행(dp[0][x])과 첫 번째 열(dp[y][0])을 초기화합니다.
- 점화식 dp[y][x] = land[y][x] + max(dp[y-1][x], dp[y][x-1])을 적용하여 dp[][]를 채웁니다.
- dp[N-1][M-1] 값을 출력합니다.
정답코드
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] land = new int[n][m];
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++){
land[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] dp = new int[n][m];
dp[0][0] = land[0][0];
for(int i=1; i<n; i++) dp[i][0] = land[i][0] + dp[i-1][0];
for(int j=1; j<m; j++) dp[0][j] = land[0][j] + dp[0][j-1];
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
dp[i][j] = land[i][j] + Math.max(dp[i-1][j], dp[i][j-1]);
}
}
System.out.println(dp[n-1][m-1]);
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
[백준] 2096번 - 내려가기 java (0) | 2025.03.10 |
---|---|
[백준] 1149번 - RGB거리 java (0) | 2025.03.09 |
[백준] 9095번 - 1, 2, 3 더하기 java (0) | 2025.03.07 |
[백준] 10026번 - 적록색약 java (0) | 2025.03.06 |
[백준] 27737번 - 버섯 농장 java (0) | 2025.03.05 |