[백준] 17070.파이프 옮기기 (java) / DP

@DP / 36m

쉬운 dp 문제인데, 생각을 잘못 해서 10분정도 헤맸다.

dp를 처음 공부할 때 좋은 문제.

 

 

문제 링크

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

17070번: 파이프 옮기기 1

 

 

구현 방법

파이프를 놓을 수 있는 방법은 3가지(가로, 대각선, 세로) 이다.

그래서 각각의 경우의 수를 저장할 수 있는 3차원 배열을 만들었다.

int[][][] dp = new int[N][N][3] => [행][열][가로:0/대각선:1/세로:2]

 

 

현재 칸을 (x, y)라 하면

1. 가로 방향

가로 방향으로 놓을 수 있는 경우는, 이전 파이프를 가로 또는 대각선으로 놓은 경우이다.

즉 [x][y-1] 칸의 [0]번째 값과 [1]번째 값을 더해주면 된다.

 

2. 대각선 방향

대각선 방향으로 놓을 수 있는 경우는, 이전 파이프가 뭐든지 상관없이 가로/대각선/세로 일때 모두 가능하다.

즉 [x-1][y-1] 칸의 [0]번째 값과 [1]번째 값, [2]번째 값을 더해주면 된다.

 

3.세로 방향

세로 방향으로 놓을 수 있는 경우는, 이전 파이프를 세로 또는 대각선으로 놓은 경우이다.

즉 [x-1][y] 칸의 [1]번째 값과 [2]번째 값을 더해주면 된다.

 

 

 

구현 포인트

1. 첫 파이프의 값을 넣고 시작한다.

dp[0][1][0] = 1;

(0, 1)칸에 가로 파이프의 끝이 있다는 의미이다.

 

 

2. 2중 for문을 돌리는데, 이때 파이프는 항상 2열부터 놓을 수 있으므로

for (i : 0~N-1)

     for (j : 2 ~ N-1)

이렇게 돌린다.

 

안쪽 for문을 j = 1부터 돌리면,

1번에서 넣어놓은 값을 dp[0][0][0] + dp[0][0][1] 로 덮어버려서 답이 계속 0이 나온다.

꼭 2부터 돌리기!!

 

 

3. 조건 추가

1) 칸에 벽이 있는 경우, 파이프를 놓을 수 없고

2) 맨 윗줄의 경우, 가로 파이프만 놓을 수 있다.

3) 또한, 대각선 파이프를 놓을 경우, 지금 칸 + 지금 칸의 윗 칸 + 지금 칸의 왼 칸 모두 벽이 없어야 한다.

 

 

 

삽질 포인트

가로 방향으로 놓는 상황에는 이전 파이프가 가로 또는 대각선으로 놓여진 경우이다.

근데 나는 이걸 착각해서

 

이전 파이프가 가로로 놓여진 경우 [x][y-1][0]

+ 이전 파이프가 대각선으로 놓여진 경우 [x-1][y-1][1]

 

으로 계산했다.. 그러니 당연히 틀리지 ㅠㅠ

 

 

지금 가로 방향으로 파이프를 놓는다는 것은, [x][y-1]칸과 [x][y]칸을 연결한다는 뜻이다.

즉, 이전 칸의 기준은  [x][y-1]칸이 되어야 한다!

 

 

코드

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

public class Main {
	
	private static int N, map[][], dp[][][];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new int[N][N][3];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		
		dp[0][1][0] = 1;
		System.out.println(dp());
	}

	private static int dp() {
		for (int i = 0; i < N; i++) {
			for (int j = 1; j < N; j++) {

				if (map[i][j] == 1) continue;
				dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][1];
				
				if (i == 0) continue;;
				dp[i][j][2] = dp[i - 1][j][1] + dp[i - 1][j][2];

				if (map[i - 1][j] == 1 || map[i][j - 1] == 1) continue;
				dp[i][j][1] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
			}
		}
		return dp[N - 1][N - 1][0] + dp[N - 1][N - 1][1] + dp[N - 1][N - 1][2];
	}
}

 

오랜만에 푼 DP문제였다.

 

끝!