티스토리 뷰

PS/백준

[백준/C++] 2339번 - 석판자르기

unside 2021. 3. 25. 00:11

오늘의 문제!

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

입력

첫째 줄에 N이 주어짐
둘째 줄부터 N개의 줄에 석판의 상태가 주어짐

풀이

전체 map에서 불순물을 찾고 불순물을 기준 가로, 세로로 자는 경우를 찾는다
불순물을 찾은경우 석판을 잘라야 하는데 자를 수 없는 경우를 먼저 판단한다

1번 - 불순물과 보석이 1개씩인 경우
2번 - 불순물만 있거나 불순물과 보석이 둘다 없는 경우
3번 - 불순물이 없고 보석이 2개 이상인 경우
4번 - 불순물을 자르고자 하는 방향에 보석이 있는 경우
5번 - 가로로 자르려고 하는데 불순물이 가장 위 또는 가장 아래에 있는 경우
6번 - 세로로 자르려고 하는데 불순물이 가장 왼쪽 또는 가장 오른쪽에 있는 경우
총 6가지의 경우는 석판을 자를 수 없는 경우이다.
그 외의 경우는 석판을 자르고 상황을 봐야한다

재귀 함수에서 끝이 되는 경우는 석판에 보석 하나만 있는 경우 1을 반환한다
석판을 자르고 상황을 봐야하는 경우에서 석판을 자르면 석판이 2가지로 나뉘어지는데 이때 경우의 수는 2개에서 나온 석판의 경우의 수의 곱이 총 경우의 수가 된다

즉, 세로로 자른경우는 왼쪽석판의 경우의 수 * 오른쪽석판의 경우의 수가 되는 것이다

소스

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
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[21][21];
 
int func(int x0, int y0, int xi, int yi, bool slice){ //slice가 참이면 가로로 잘랐음, slice가 거짓이면 세로로 잘랐음
    int impurities=0, jewel=0; //불순물, 보석
    for(int y=y0;y<yi;y++){
        for(int x=x0;x<xi;x++){
            if(map[y][x] == 2){ //보석있음
                jewel++;
            }
            else if(map[y][x] == 1){ //불순물있음
                impurities++;
            }
        }
    }
    
    if(jewel == 1 && impurities == 0){ //불순물없고 보석있음 - 진행가능
        return 1;
    }
    else if(jewel == 1 && impurities == 1){ //불순물과 보석이 1개씩이므로 - 진행불가
        return 0;
    }
    else if(jewel == 0){ //불순물만 있거나 둘다 없음 - 진행불가
        return 0;
    }
    else if(jewel > 2 && impurities == 0){
        return 0;
    }
    //불순물과 쥬얼이 여러개 - 석판 나눠봐야 앎
    int result = 0;
    for(int y=y0;y<yi;y++){
        for(int x=x0;x<xi;x++){
            if(map[y][x] == 1){//불순물
                if(slice){ //이전에 가로로 잘랐기 때문에 그다음은 세로만 가능
                    //세로로 자를 수 있는가?
                    if(x!=x0 && x!=xi-1){ //양끝이 아니라서 1차합격
                        bool check = true;
                        for(int i=y0;i<yi;i++){
                            if(map[i][x] == 2){ //세로에 보석이 있어서 불가능
                                check = false;
                                break;
                            }
                        }
                        if(check){ //세로에 보석이 없어서 2차합격
                            result = result + func(x0, y0, x, yi, false)*func(x+1, y0, xi, yi, false);
                        }
                    }
                }
                else{ //이전에 세로로 잘랐기 때문에 그다음은 가로만 가능
                    //가로로 자를 수 있는가?
                    if(y!=y0 && y!=y-1){ //양끝이 아니라서 1차합격
                        bool check = true;
                        for(int i=x0;i<xi;i++){
                            if(map[y][i] == 2){ //가로에 보석이 있어서 불가능
                                check = false;
                                break;
                            }
                        }
                        if(check){//가로에 보석이 없어서 2차합격
                            result = result + func(x0, y0, xi, y, true)*func(x0, y+1, xi, yi, true);
                        }
                    }
                }
            }
        }
    }
    return result;
}
 
int main(void){
    int N,imp=0,jew=0;
    cin >> N;
    for(int y=0;y<N;y++){
        for(int x=0;x<N;x++){
            cin >> map[y][x];
            if(map[y][x] == 2){
                jew++;
            }
            else if(map[y][x] == 1){
                imp++;
            }
        }
    }
    if(imp==0 && jew == 1){
        cout << 1;
    }
    else{
        int resultA = func(0,0,N,N,true);
        int resultB = func(0,0,N,N,false);
        if(resultA + resultB == 0){
            cout << -1;
        }
        else{
            cout << resultA + resultB;
        }
    }
    return 0;
}
 
 
cs
저작자표시 비영리 동일조건

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

[백준/C++] 1699번 - 제곱수의 합  (0) 2021.03.29
[백준/C++] 11052번 - 카드 구매하기  (0) 2021.03.29
[백준/C++] 1992번 - 쿼드트리  (0) 2021.03.23
[백준/C++] 1725번 - 히스토그램  (0) 2021.03.20
[백준/C++] 2104번 - 부분배열 고르기  (0) 2021.03.19
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/02   »
일 월 화 수 목 금 토
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
글 보관함