import java.io.*;
import java.util.*;
classMain{
staticint[] dx = {0, -1, 0}, dy = {1, 0, -1}; // bfs를 위한 델타 배열 생성(위로는 못 올라감)staticint[][] mm, arr;
staticint N, M;
publicstaticvoidmain(String[] args)throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = newint[N][M]; // 유적 금화를 저장하는 배열
mm = newint[N][M]; // 메모이제이션(위치, 방향 저장)// 유적 내 금화 저장for(int i=0;i<N;i++) {
st = new StringTokenizer(bf.readLine());
for(int j=0;j<M;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
boolean[][] visited = newboolean[N][M];
visited[N-1][M-1] = true;
mm[0][0] = arr[0][0];
System.out.println((1000000000+dp(N-1, M-1, visited)));
}
publicstaticintdp(int x, int y, boolean[][] visited){
// if(mm[x][y] != 0) return mm[x][y];int returnVal = arr[x][y];
int maxRoute = 0;
// 현 위치 기준 좌, 우, 상 에서 내려오는 경우 중 가장 큰 값 체크for(int i=0;i<3;i++) {
int nX = x+dx[i];
int nY = y+dy[i];
if(isInRange(nX, nY) && !visited[nX][nY]) {
visited[nX][nY] = true;
maxRoute = Math.max(maxRoute, dp(nX, nY, visited));
visited[nX][nY] = false;
}
}
// if(x == N-1 && y == M-1) {// for(int i=0;i<N;i++) {// for(int j=0;j<M;j++) {// System.out.print(visited[i][j]+" ");// }// System.out.println();// }// }return mm[x][y] = returnVal + maxRoute;
}
publicstaticbooleanisInRange(int x, int y){
return0 <= x && x < N && 0 <= y && y < M;
}
}
일단 저는 메모이제이션을 통해 탑다운 방식으로 풀어보려 했어요.
(N-1, M-1) 에서의 최댓값을 구하려면, (N-2, M-1) 과 (N-1, M-2)에서의 최댓값 중 더 큰 것을 고르면 된다고 생각했습니다.
하지만 여기서 논리적인 오류가 발생하는데..
(0, 0)에서 시작한다.
(N-1, M-1)에서의 최댓값을 가지는 경로가 (a, b)를 지난다고 가정했을 때, (a, b)에서의 최댓값을 가지진 않을 수 있다.
이 두 가지를 고려하지 않았습니다...
예를 들어봅시다.
3 5
1 1 1 3 4
0 0 5 2 -1
0 0 1 1 1
의 input이 있다고 가정합니다.
제 코드로 돌려본다면, 12라는 output이 나오게 됩니다.
하지만 정답은 19 입니다.
네
그냥 설계부터 잘못된 코드입니다!
아무튼 그래서 다른 방법을 찾게되었고,
가장 첫 행에서는 왼쪽에서 오른쪽으로밖에 이동할 수 없다.
라는 점을 깨달았습니다.
// 가장 첫 행 계산하기 -> 우측으로밖에 가지 못함
mm[0][0] = arr[0][0];
for(int i=1;i<M;i++) {
mm[0][i] = mm[0][i-1] + arr[0][i];
}
그래서 mm 배열 중 가장 첫 행은, 직전 값에 해당 칸의 value를 더한 값으로 업데이트 해줬습니다.
다음 행부터는 가짓수가 증가합니다.
왼쪽에서 오른쪽으로 이동하거나
오른쪽에서 왼쪽으로 이동하거나
위에서 아래로 이동한다.
이 세 가지입니다.
위에서 아래로 순차적으로 내려올 수 있기 때문에,
두 번째 행부터 차근차근 계산을 해줄겁니다.
각 행마다 fromLeft (왼쪽에서 오른쪽), fromRight (오른쪽에서 왼쪽) 배열을 만들어줍니다.
fromLeft의 가장 왼쪽 값과, fromRight에서 가장 오른쪽 값은, 위에서밖에 내려와 업데이트 되지 못합니다.
public class Main { static int arr[], parent[]; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(bf.readLine()); int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken()); arr = new int[N]; parent = new int[N]; for(int i=0;i<N;i++) { arr[i] = Integer.parseInt(bf.readLine()); parent[i] = i; } for(int i=0;i<M;i++) { st = new StringTokenizer(bf.readLine()); int a = Integer.parseInt(st.nextToken())-1, b = Integer.parseInt(st.nextToken())-1; int fa = find(a), fb = find(b);
