[백준/JAVA] 17484번: 진우의 달 여행 (Small)
🔺 문제
17484번: 진우의 달 여행 (Small)
첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int map[][];
static int dp[][][];
static int max = 999999;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// dp 배열 초기화
dp = new int[n][m][3];
for (int i = 0; i < m; i++) {
dp[0][i][0] = map[0][i]; // 왼쪽 대각선
dp[0][i][1] = map[0][i]; // 가운데
dp[0][i][2] = map[0][i]; // 오른쪽 대각선
}
// dp 배열 채우기
for (int i = 1; i < n; i++) {
// max 값으로 초기화
dp[i][0][0] = max;
dp[i][m - 1][2] = max;
for (int j = 0; j < m; j++) {
// 오른쪽에서 못 오는 경우
if (!(j - 1 < 0 || j - 1 >= m) && (j + 1 < 0 || j + 1 >= m)) {
dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + map[i][j];
dp[i][j][1] = Math.min(dp[i - 1][j][0] , dp[i - 1][j][2]) + map[i][j];
}
// 양쪽에서 올 수 있는 경우
else if (!(j - 1 < 0 || j - 1 >= m) && !(j + 1 < 0 || j + 1 >= m)) {
dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + map[i][j];
dp[i][j][1] = Math.min(dp[i - 1][j][0] , dp[i - 1][j][2]) + map[i][j];
dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + map[i][j];
}
// 왼쪽에서 못오는 경우
else if ((j - 1 < 0 || j - 1 >= m) && !(j + 1 < 0 || j + 1 >= m)) {
dp[i][j][1] = Math.min(dp[i - 1][j][0] , dp[i - 1][j][2]) + map[i][j];
dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + map[i][j];
}
}
}
// 마지막 행에서 최소값 찾기
int min = max;
for (int i = 0; i < m; i++) {
for (int j = 0; j < 3; j++) {
min = Math.min(min, dp[n - 1][i][j]);
}
}
System.out.println(min);
}
}
|
cs |
✅ 해결 아이디어
✔ DP
- DP 배열을 최솟값으로 채우기
🔺 다른 풀이들
- DFS 풀이
[BOJ/Python, Java] 백준 17484번 - 진우의 달 여행 (Small)
백준 #17484 진우의 달 여행 (Small) 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이
amor-fati.tistory.com
[알고리즘] Java / 백준 / 진우의 달 여행 (Large) / 17485
문제문제 링크접근 방식우주선이 연속으로 같은 방향을 가면 안되기 때문에 각각의 2차원 배열에 각 방향을 의미하는 3 크기의 배열을 넣는다 ( 0 : 왼쪽에서 내려옴, 1 : 가운데서 내려옴, 2 : 오
velog.io
💬 느낀 점
DP 문제인 거 캐치하고... 좀 고민하다가...
내 풀이로 안 풀려서 다른 분 풀이 보고 두통 해결....
복습허자,,,
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
✔ 풀이 참고
[백준] S3 17484번 진우의 달 여행 (Small) (JAVA)
문제 출처 - Baekjoon Online Judge 문제는 여기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [문제] 우주비행이 꿈이였던 진우는 음식점 '매
blackvill.tistory.com