백준 21317번: 징검다리 건너기

문제 설명

• https://www.acmicpc.net/problem/21317
• 1번부터 N번까지 이동해야 합니다.
  모든 위치에서는 에너지를 소비해 한칸 또는 두칸 이동할 수 있습니다.
  모든 위치에서 딱 한번 세칸 이동할 수 있습니다.

접근법

• 세 칸 점프를 할 수 있다는 조건이 존재합니다. 조건을 행으로 두는 dp배열을 만들어 문제를 해결할 수 있습니다.
  • dp[j][i] = 세 칸 점프를 j번 사용해 i번째 칸까지 이동하는 최소값

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] board = new int[2][Math.max(4,N)];
		for (int i = 1; i <= N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			board[0][i] = Integer.parseInt(st.nextToken());
			board[1][i] = Integer.parseInt(st.nextToken());
			
		}
//		for (int i = 0; i < board.length; i++) {
//			System.out.println(Arrays.toString(board[i]));
//		}
		
		int K = Integer.parseInt(br.readLine());
		
		int[][] dp = new int[2][Math.max(4, N+1)];
		for (int i = 0; i < dp.length; i++) {
			Arrays.fill(dp[i], 10000);
		}
		dp[0][0] = 0;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 0;
		dp[0][2] = board[0][1];
		dp[0][3] = Math.min(dp[0][2] + board[0][2], dp[0][0]+board[1][1]);
		for (int i = 4; i <= N; i++) {
			dp[0][i] = Math.min(dp[0][i-1] + board[0][i-1], dp[0][i-2] + board[1][i-2]);
			dp[1][i] = Math.min(Math.min(dp[1][i-1] + board[0][i-1], dp[1][i-2] + board[1][i-2]),dp[0][i-3]+K);
		}
		int answer = Math.min(dp[0][N], dp[1][N]);
		System.out.println(answer);
//		
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		
		
	}
}