아이디어

• 구하는 값은 이전까지 구했던 힘의 합에 새로 밟는 움직임에 대한 힘을 더하는 형태로 이루어진다.
  • 즉, 부분 중복문제, 최적 부분문제의 형태를 띄고 있다.
• DP를 생각하여, 필요한 변수를 생각해보면, 현재 길이, 왼발과 오른발의 위치에 영향을 받음을 알 수 있다. 따라서 3차원 동적 테이블을 이용한다.
  • 사실, 현재 길이는 항상 이전의 값만 참조하는 것이므로, 변수로 고려하지 않아도 된다.
  • 그러나 메모리가 넉넉하므로 편의를 위해 길이에 대한 차원도 고려한다.
• 지문에선 '힘'에 대해 복잡하게 설명되어 있는데, 간단히 $i$번 칸에서 $j$번 칸으로 발을 옮기는 데 드는 힘을 $P_{ij}$라 하면 $P_{ij}$는 다음과 같이 쓸 수 있다. ($0 \leq i, j \leq 4$, $\infty$는 움직일 수 없음)
  $P_{ij} = \begin{bmatrix} \infty & 2 & 2 & 2 & 2 \\ \infty & 1 & 3 & 4 & 3 \\ \infty & 3 & 1 & 3 & 4 \\ \infty & 4 & 3 & 1 & 3 \\ \infty & 3 & 4 & 3 & 1 \end{bmatrix}$
• 현재 왼발과 오른발이 각각 움직이려는 칸과 같을 때에만 이전의 값을 이용해 힘의 최솟값을 갱신한다.

코드

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static final int INF = Integer.MAX_VALUE / 2;
	static int[][] P = {
			{INF, 2, 2, 2, 2},
			{INF, 1, 3, 4, 3},
			{INF, 3, 1, 3, 4},
			{INF, 4, 3, 1, 3},
			{INF, 3, 4, 3, 1}
	};
	
	static int N, ans;
	static int[] O = new int[100_002];
	static int[][][] memo;	// [len][L][R]
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		while (tk.hasMoreTokens()) {
			O[++N] = Integer.parseInt(tk.nextToken());
		}
		N--;
		
		memo = new int[N+1][5][5];
		for (int l=0; l<=4; l++)
			for (int r=0; r<=4; r++)
				memo[0][l][r] = INF;
		memo[0][0][0] = 0;
		
		for (int i=1; i<=N; i++) {
			for (int l=0; l<=4; l++) {
				for (int r=0; r<=4; r++) {
					memo[i][l][r] = INF;
					if (l == O[i]) {
						for (int pl=0; pl<=4; pl++)
							memo[i][l][r] = Math.min(memo[i][l][r], memo[i-1][pl][r] + P[pl][l]);	
					}
					if (r == O[i]) {
						for (int pr=0; pr<=4; pr++)
							memo[i][l][r] = Math.min(memo[i][l][r], memo[i-1][l][pr] + P[pr][r]);	
					}	
				}
			}
		}
		
		ans = INF;
		for (int l=0; l<=4; l++) {
			for (int r=0; r<=4; r++) {
				ans = Math.min(ans, memo[N][l][r]);
			}
		}
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 48508 KB
• 시간: 412 ms

리뷰

• 입력을 받는 방식이 특이해서 주의해야 하는 문제
  • 처음에 tk.tokenCount() > 1인지로 판단했다가, 시간초과가 났었다.
• 위에서 말했던 거처럼 2차원 동적 테이블 2개를 번갈아가며 사용하는 형태로 바꾼다면 메모리를 크게 줄일 수 있을 것이다.
• 내 풀이에서는 상향식으로 했는데, 하향식 코드(재귀)를 쓰는 게 오히려 시간이 줄어들 것 같다.