β¨ DP
https://www.acmicpc.net/problem/2169
2169λ²: λ‘λ΄ μ‘°μ’ νκΈ°
첫째 μ€μ N, M(1≤N, M≤1,000)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ Mκ°μ μλ‘ λ°°μ΄μ΄ μ£Όμ΄μ§λ€. λ°°μ΄μ κ° μλ μ λκ°μ΄ 100μ λμ§ μλ μ μμ΄λ€. μ΄ κ°μ κ·Έ μ§μμ κ°μΉλ₯Ό λνλΈλ€.
www.acmicpc.net
π κ³ λ €ν΄μΌν μ¬ν
- λ‘λ΄μ μμ§μΌ λ λ°°μ΄μμ μΌμͺ½, μ€λ₯Έμͺ½, μλμͺ½μΌλ‘ μ΄λν μ μμ§λ§ μμͺ½μΌλ‘λ μ΄λ X
- ν λ² νμ¬ν μ§μμ μ¬νμ¬ X
- (1, 1)μμ (N, M)κΉμ§ κ° λ νμ¬ν μ§μλ€μ κ°μΉμ μ΅λκ° κ΅¬νκΈ°
πΉοΈ νμ΄ λ°©λ²
μ°μ 0λ²μ§Έ νμ μλ κ°λ€μ μΌμͺ½μμλΆν° μ΄λνλ©΄μ ν©μ³μ§ κ°μ κΈ°λ‘νλ€. μ΄λ―Έ νμν κΈΈμ λ€μ λ°©λ¬Έν μ μμΌλ―λ‘ κ²½λ‘κ° μΌμͺ½μΌλ‘λΆν° μ΄λν κ²λ§ μ‘΄μ¬νκΈ° λλ¬Έμ΄λ€.
dpλ₯Ό νμ©ν΄ νλ©΄ λλ―λ‘ μ°μΈ‘ κ·Έλ¦Όμ²λΌ νμ¬ (i, j) μΉΈ κΈ°μ€μΌλ‘ μΌμͺ½(i, j-1), μ€λ₯Έμͺ½(i, j+1), μμͺ½(i-1, j)μ μλ κ°κ³Ό νμ¬ μΉΈμ μλ κ°μ λνμ¬ λ ν° κ°μΌλ‘ κ°±μ μμΌμ£Όλ©΄ λλ€.
νμ§λ§ ν κ°μ§ λ κ³ λ €ν΄μΌν μ μ΄ μλ€.
νμ¬ μΉΈ κΈ°μ€μΌλ‘ μ€λ₯Έμͺ½μ μλ μΉΈμ κ°±μ λκΈ° μ μ κ°μ΄λ€.
λ§μ½ μ€λ₯Έμͺ½μ μλ μκ° λ ν° κ°μΌλ‘ κ°±μ λλ€λ©΄ νμ¬ μΉΈλ λ€μ κ°±μ μμΌμ£Όμ΄μΌ νλλ° κ·Έλ κ² λλ©΄ μλΉν 볡μ‘ν΄μ§ κ²μ΄λ€.
κ·Έλ¬λ―λ‘ temp[2][j] λ°°μ΄μ μμ±νμ¬ temp[0][j]μλ μΌμͺ½, μμͺ½μΌλ‘λΆν° λν κ°μ,
temp[1][j]μλ μ€λ₯Έμͺ½, μμͺ½μΌλ‘λΆν° λν κ°μ λ£κ³ λ κ°μ λ°°μ΄μ λΉκ΅νμ¬ μ΅μ’ μ μΌλ‘ ν° κ°μ dp[i][j]μ λ£μ΄μ£Όλ©΄ λλ€.
κ·Έλ¬λ©΄ μμ κ°μ κ²°κ³Όκ° λμ¨λ€.
π©π» μ 체 μ½λ
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class BOJ_2169_λ‘λ΄μ‘°μ’
νκΈ° {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] robot = new int[N][M];
int[][] dp = new int[N][M];
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++){
robot[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][0] = robot[0][0];
// 0λ²μ§Έ ν κ° μ±μ°κΈ°
for(int i=1; i<M; i++){
dp[0][i] = robot[0][i]+dp[0][i-1];
}
int[][] temp = new int[2][M];
for(int i=1; i<N; i++){
// μ’&μ
temp[0][0] = robot[i][0]+dp[i-1][0];
for(int j=1; j<M; j++){
temp[0][j] = Math.max(temp[0][j-1], dp[i-1][j])+robot[i][j];
}
// μ°&μ
temp[1][M-1] = robot[i][M-1]+dp[i-1][M-1];
for(int j=M-2; j>=0; j--){
temp[1][j] = Math.max(temp[1][j+1], dp[i-1][j])+robot[i][j];
}
for(int j=0; j<M; j++){
dp[i][j] = Math.max(temp[0][j], temp[1][j]);
}
}
bw.write(dp[N-1][M-1] + " ");
bw.flush();
bw.close();
}
}
'μκ³ λ¦¬μ¦ > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] 1202 보μλλ - Java (1) | 2024.04.19 |
---|---|
[BOJ] 1238 νν° - Java (0) | 2024.04.18 |
[BOJ] 14503 λ‘λ΄μ²μκΈ° - Java (0) | 2024.04.11 |
[BOJ] 19238 μ€ννΈ νμ - Java (0) | 2024.04.11 |
[BOJ] 17837 μλ‘μ΄ κ²μ2 - Java (0) | 2024.03.19 |