[BOJ/Java] 17070 : 파이프 옮기기1

 

문제

 

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

풀이

 

여러가지 풀이가 있지만 난 DP로 풀었다 / map[i][j]를 기준으로 해당 위치에 파이프가 가로/세로/대각선으로 위치할 수 있는 경우의 수를 DP로 더해나간다

 

 

코드

 

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

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n;
	static int[][] map;
	static int pipeX, pipeY;

	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(in.readLine());
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Pipe[][] dp = new Pipe[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 1; j < n; j++) {
				if (map[i][j] == 1) {
					dp[i][j] = new Pipe(0, 0, 0);
					continue;
				}
				if (i == 0 && j == 1) {
					dp[0][1] = new Pipe(1, 0, 0);
					continue;
				}

				dp[i][j] = new Pipe(0,0,0);

				if (j - 1 > 0) {// 가로
					if (map[i][j - 1] == 0)
						dp[i][j].horizontal += dp[i][j - 1].horizontal + dp[i][j - 1].diagnal;
				}
				if (i - 1 >= 0) {// 세로
					if (map[i - 1][j] == 0)
						dp[i][j].vertical += dp[i - 1][j].vertical + dp[i - 1][j].diagnal;
				}
				if (i - 1 >= 0 && j - 1 > 0) {// 대각선
					if (map[i - 1][j - 1] == 0 && map[i - 1][j] == 0 && map[i][j - 1] == 0)
						dp[i][j].diagnal += dp[i - 1][j - 1].horizontal + dp[i - 1][j - 1].vertical
								+ dp[i - 1][j - 1].diagnal;
				}
			}
		}

/*		for (int i = 0; i < n; i++) {
			for (int j = 1; j < n; j++) {
				System.out.print(
						"(" + dp[i][j].horizontal + "," + dp[i][j].vertical + "," + dp[i][j].diagnal + ")" + " ");
			}
			System.out.println();
		}
*/
		System.out.println(dp[n - 1][n - 1].horizontal + dp[n - 1][n - 1].vertical + dp[n - 1][n - 1].diagnal);

	}

	static class Pipe {
		int horizontal;
		int vertical;
		int diagnal;

		Pipe() {
		}

		Pipe(int h, int v, int d) {
			horizontal = h;
			vertical = v;
			diagnal = d;
		}
	}
}

 

 

느낀점

 

• DP가 익숙하지 않아서 규칙을 찾기 어렵다