백준 삼각 그래프(4883)

 

dp 문제를 풀었다.

 

https://www.acmicpc.net/problem/4883

4883번: 삼각 그래프

 

처음 가운데 중앙에서 마지막 가운데 중앙까지 가는 최단경로를 찾는 문제이다.

 

처음 dp배열라인에 값을 설정하고 증가시키는 방법으로 진행하려고 생각했다.

 

각 왼 중 오 3개의 포인트에서 어떤 루트로 들어와야 가장 값이 낮을수있을까 생각을 해봐야한다.

 

현재라인 h높이라 할때

 

왼 :  dp[h-1][0], dp[h-1][1] 

중 : dp[h][0], dp[h-1][0], dp[h-1][1], dp[h-1][2]

오: dp[h][1], dh[h-1][1] , dh[h-1][2] 

 

에서 최소값을 계속 더해주면서 진행하면 되겠다고 생각했다.

 

중요한점 dp[0][0]은 처음 시작점으로 설정 하면 안되기에 큰값을 넣어 제외시키는 방법을 선택했다.

 

필자는 출력시 앞에 순번 카운트를 안해서 계속 실패떳다.. 또 헛시간 날렸다

 

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
 * https://www.acmicpc.net/problem/4883
 */
public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int no = 1;
        while (true) {

            int N = Integer.parseInt(br.readLine());

            if (N == 0) {
                bw.flush();
                return;
            }

            int[][] map = new int[N][3];
            int[][] dp = new int[N][3];

            for (int i=0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                map[i][0] = Integer.parseInt(st.nextToken());
                map[i][1] = Integer.parseInt(st.nextToken());
                map[i][2] = Integer.parseInt(st.nextToken());
            }

            dp[0][0] = Integer.MAX_VALUE;
            dp[0][1] = map[0][1];
            dp[0][2] = Math.min(map[0][1] + map[0][2], dp[0][1] + map[0][2]);

            for (int i=1; i < N; i++) {
                dp[i][0] = Math.min(dp[i-1][0], dp[i-1][1]) + map[i][0];
                dp[i][1] = Math.min(dp[i][0], Math.min(dp[i-1][2], Math.min(dp[i-1][0], dp[i-1][1]))) + map[i][1];
                dp[i][2] = Math.min(dp[i][1], Math.min(dp[i-1][1], dp[i-1][2])) + map[i][2];
            }

            int answer = dp[N-1][1];

            bw.write(no + ". " + answer + "\n");
            no++;
        }

    }
}

 

결과