반응형

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

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제는 여러 가지 방법으로 풀 수 있습니다. dfs를 이용하여 모든 경우의 수를 다 구할 수도 있고, dp를 이용해서 더 빠르게 풀 수도 있습니다.

 

그중 dp를 이용한 방법에 대해서 설명드리겠습니다. 어떤 한 좌표에 파이프가 올 수 있는 경우의 수를 dp [ state ][ y ][ x ] 배열에 각각 저장하면서 마지막에 dp [ 0 ][ N ][ N ] + dp [ 1 ][ N ][ N ] + dp [ 2 ][ N ][ N ]을 출력하면 됩니다. 

 

먼저 한 점 y, x에 올 수 있는 파이프의 개수를 저장하기 위해서는 각각의 상황에 따라 다르게 구해주어야합니다.

 

예를 들어 0번 상태(가로) 일 때는 1번 상태(세로)의 파이프는 올 수 없습니다. 따라서, dp [ 0 ][ y ][ x ] = dp[ 0 ][ y ][ x - 1 ] + dp[ 2 ][ y ][ x - 1 ]이 됩니다. 마찬가지로 나머지 상태에서도 값을 구해주면 답을 얻을 수 있습니다.

 

다음 소스 코드에는 두 가지 방법을 모두 나타내었습니다. 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
 
using namespace std;
 
int N;
int arr[17][17];
int dp[3][17][17];            //각 상태를 저장할 dp배열 [state][y][x] state 0:가로 1:세로 2:대각
 
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
 
    dp[0][1][2] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j] != 1) {        //파이프가 움직일 수 있을 때만
                dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];    //가로, 대각
                dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];    //세로, 대각
                if (arr[i - 1][j] != 1 && arr[i][j - 1] != 1) {
                    for (int k = 0; k < 3; k++) {
                        dp[2][i][j] += dp[k][i - 1][j - 1];        //가로, 세로, 대각
                    }
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += dp[i][N][N];
    }
 
    cout << ans;
}
 
//#include <iostream>
//
//using namespace std;
//
//int N;
//int arr[16][16];
//int dp[3][16][16];
//int dx[3] = { 1,0,1 };
//int dy[3] = { 0,1,1 };
//
//void dfs(int state, int y, int x)
//{
//    if (dp[state][y][x] != -1) return;
//
//    int cur = 0;
//
//    if (state != 1 && arr[y][x + 1] == 0 && x + 1 < N) {
//        dfs(0, y, x + 1);
//        cur += dp[0][y][x + 1];
//    }
//
//    if (state != 0 && arr[y + 1][x] == 0 && y + 1 < N) {
//        dfs(1, y + 1, x);
//        cur += dp[1][y + 1][x];
//    }
//
//    bool flag = true;
//
//    for (int i = 0; i < 3; i++) {
//        int yy = y + dy[i];
//        int xx = x + dx[i];
//        if (arr[yy][xx] != 0) {
//            flag = false;
//            break;
//        }
//    }
//
//    if (flag && x + 1 < N && y + 1 < N) {
//        dfs(2, y + 1, x + 1);
//        cur += dp[2][y + 1][x + 1];
//    }
//
//    dp[state][y][x] = cur;
//}
//
//int main()
//{
//    cin >> N;
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < N; j++) {
//            cin >> arr[i][j];
//            for (int k = 0; k < 3; k++) {
//                if (i == N - 1 && j == N - 1) {
//                    dp[k][i][j] = 1;
//                }
//                else {
//                    dp[k][i][j] = -1;
//                }
//            }
//        }
//    }
//
//    dfs(0, 0, 1);
//
//    cout << dp[0][0][1];
//}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 11054번 - 가장 긴 바이토닉 부분 수열 (C++)  (0) 2022.06.05
[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 9251번 - LCS (C++)  (0) 2022.06.02
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31

+ Recent posts

티스토리툴바