โจ 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 |
โจ 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 |