Notice
Recent Posts
Recent Comments
Link
알고리즘 모음(C++)
백준 17069 - 파이프 옮기기 2(C+) 본문
문제 링크입니다. https://www.acmicpc.net/problem/17069
파이프 옮기기 1(https://www.acmicpc.net/problem/17070)와 거의 유사한 문제였습니다.
배열 칸을 늘리고, 답의 데이터 형식을 long long int로 바꿔주면 되는 문제입니다.
문제 풀이 방식은 해당 문제와 같습니다. https://junseok.tistory.com/178
자세한 것은 코드를 참고해주세요
#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;
}
질문 및 조언 댓글 남겨주세요
'백준' 카테고리의 다른 글
백준 1991 - 트리 순회(C++) (0) | 2022.02.22 |
---|---|
백준 2096 - 내려가기(C++) (0) | 2022.02.22 |
백준 17070 - 파이프 옮기기 1(C++) (0) | 2022.02.21 |
백준 2108 - 통계학(C++) (0) | 2022.02.21 |
백준 12851 - 숨바꼭질 2(C++) (0) | 2022.02.20 |