백준 17069 - 파이프 옮기기 2(C+)

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

17069번: 파이프 옮기기 2

파이프 옮기기 1(https://www.acmicpc.net/problem/17070)와 거의 유사한 문제였습니다.

배열 칸을 늘리고, 답의 데이터 형식을 long long int로 바꿔주면 되는 문제입니다.

문제 풀이 방식은 해당 문제와 같습니다. https://junseok.tistory.com/178

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

 

 

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

#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;
long long int dp[33][33][3]; // 0 - 가로 , 1 - 세로 , 2 - 대각선
int map[33][33];

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] == 1) return;
			for (int i = 0; i < 3; i++) {
				dp[x][y][way] += dp[x - 1][y - 1][i];
			}
		}
	}
}

void solve() {
	long long 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;
}

 

 

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