백준 17070 - 파이프 옮기기 1(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

다이나믹 프로그래밍 문제입니다.

(X , Y)로 올 수 있는 파이프의 종류가 3개이니, 3개의 경우로 나눠서 풀어야하는 문제였습니다.

 

좌표 (X , Y)가 있을 때, 해당 좌표에 도달할 수 있는 경우는 3가지입니다.

1. 가로 파이프로 도달

2. 세로 파이프로 도달

3. 대각선 파이프로 도달

각각의 경우에는 조건이 있습니다.

가로 파이프로 도달했을 경우는 이전 파이프가 가로 or 대각선이여야 되며, 세로 파이프로 도달했을 경우는 이전 파이프가 세로 or 대각선이여야 합니다. 대각선인 경우는 (X-1 , Y) && (X , Y-1)의 좌표가 비어있어야 합니다.

 

따라서 저는 Dp[X][Y][3]의 3차원 배열을 만들어서, Dp[X][Y][0] -> 가로, Dp[X][Y][1] -> 세로, Dp[X][Y][2] -> 대각선을 관리하게 했습니다.

 

void move_pipe(int x, int y, int way) {
	if (way == 0) {
		if (x >= 1 && y - 1 >= 1) dp[x][y][way] = dp[x][y - 1][0] + dp[x][y - 1][2];
	}
	else if (way == 1) {
		if (x - 1 >= 1 && y >= 1) dp[x][y][way] = dp[x - 1][y][1] + dp[x - 1][y][2];
	}
	else {
		if (x - 1 >= 1 && y - 1 >= 1) {
			if (map[x - 1][y] == 1 || map[x][y - 1]) return;
			for (int i = 0; i < 3; i++) {
				dp[x][y][way] += dp[x - 1][y - 1][i];
			}
		}
	}
}

따라서, way를 통해 어느 방향으로 놓을 건지를 결정하고 방향에 따른 조건을 만족했을 때, 나올 수 있는 경우를 더해주는 방식으로 풀었습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

int N;
int dp[17][17][3]; // 0 - 가로 , 1 - 세로 , 2 - 대각선
int map[17][17];

void move_pipe(int x, int y, int way){
	if(way == 0){
		if(x >= 1 && y-1 >= 1) dp[x][y][way] = dp[x][y-1][0] + dp[x][y-1][2];
	}
	else if(way == 1){
		if(x - 1 >= 1 && y >= 1) dp[x][y][way] = dp[x-1][y][1] + dp[x-1][y][2];
	}
	else{
		if(x - 1 >= 1 && y - 1 >= 1){
			if(map[x-1][y] == 1 || map[x][y-1]) return;
			for(int i = 0; i < 3; i++){
				dp[x][y][way] += dp[x-1][y-1][i];
			}
		}
	}
}

void solve(){
	int ans = 0;
	dp[1][2][0] = 1;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			if((i == 1 && j == 1) || (i == 1 && j == 2)) continue;
			if(map[i][j] == 1) continue;
			for(int k = 0; k < 3; k++){
				move_pipe(i,j,k);		
			}
		}
	}
	for(int i = 0; i < 3; i++){
		ans += dp[N][N][i];
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요