[JAVA] 17484번 - 진우의 달 여행 (Small)

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

1.dp로 풀어야하는것 같아서 dp로 접근했다.

2. 그런데 문제 조건은 연속으로 같은 방향으로 이동이 안된다. 이 경우를 어떻게 처리해야할 지 고민했다

-> 삼차원 배열을 생성하여 1일때는 왼쪽에서 오는경우, 2일때는 위에서 오는 경우, 3일때는 오른쪽에서 오는 경우로 처리하면 된다. 

 

 

시간복잡도

dp연산할때 이중반복문이다. O(n*m)이다

n과 m은 최대 6이니 O(36)=상수시간에 가깝게 처리할 수 있다. 1초안에 충분히 가능하다. 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. dp배열 생성

-> 삼차원으로 만들고 미리 최대값으로 채워둔다.

int [][][] dp = new int[n+1][m+1][4];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                Arrays.fill(dp[i][j], Integer.MAX_VALUE);
            }
        }

2. 첫번째 행 초기화

-> arr의 첫번째행으로 초기화시킨다.

for(int i=1; i<=m; i++) {
        	dp[1][i][1] = arr[1][i];
        	dp[1][i][2] = arr[1][i];
        	dp[1][i][3] = arr[1][i];
        }

 

3.dp 구하기

-> 삼차원으로 푸니까 머리가 너무 아팠다...^^

 

 

 

 

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

1회차 시도

-> 배열의 범위를 초과하는 경우도 생각하지 못했고, 점화식도 잘못 설계했다.

for(int i=1; i<=n; i++) {
        	for(int j=1; j<=m; j++) {
        		//왼쪽에서 오는경우: 왼쪽에서 오는 경우 제외하고 비교해서 구한다 
        		dp[i][j][1] = Math.min(dp[i-1][j][2]+arr[i][j], dp[i-1][j+1][3]+arr[i][j]);
        		//바로 위에서 오는경우
        		dp[i][j][2] = Math.min(dp[i-1][j-1][1]+arr[i][j], dp[i-1][j+1][3]+arr[i][j]);
        		//오른쪽에서 오는 경우
        		dp[i][j][3] = Math.min(dp[i-1][j-1][1]+arr[i][j], dp[i-1][j][2]+arr[i][j]);
        	}
        }

 

 

정답 코드

import java.io.*;
import java.util.*;

public 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 [][] arr = new int[n+1][m+1];
        for(int i=1; i<=n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=1; j<=m; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        int [][][] dp = new int[n+1][m+1][4];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                Arrays.fill(dp[i][j], Integer.MAX_VALUE);
            }
        }
        for(int i=1; i<=m; i++) {
        	dp[1][i][1] = arr[1][i];
        	dp[1][i][2] = arr[1][i];
        	dp[1][i][3] = arr[1][i];
        }
    
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 왼쪽에서 오는 경우
                if (j > 1) {
                    dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j - 1][2], dp[i - 1][j - 1][3]) + arr[i][j]);
                }
                // 위에서 오는 경우
                dp[i][j][2] = Math.min(dp[i][j][2], Math.min(dp[i - 1][j][1], dp[i - 1][j][3]) + arr[i][j]);
                // 오른쪽에서 오는 경우
                if (j < m) {
                    dp[i][j][3] = Math.min(dp[i][j][3], Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j]);
                }
            }
        }
       
        int minFuel= Integer.MAX_VALUE;
        for(int i=1; i<=m; i++) {
        	 minFuel = Math.min(minFuel, Math.min(dp[n][i][1], Math.min(dp[n][i][2], dp[n][i][3])));
        }
        System.out.println(minFuel);
             		
    }
}