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


이차원 배열로 주어지는 격자에서, 모든 테트로미노 모양을 다 넣어보면 된다.


주어지는 다섯개의 테트로미노를 회전 또는 대칭해서 얻을 수 있는 모양들까지 포함해서 계산해주면 된다.


가능한 모양은 총 19개이다.


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
#include<iostream>
#include<vector>
using namespace std;
int row, col, m[501][501];
int Max = -1;
 
//가능한 모양은 총 19개이다
vector<int> vr[19] = { { 1,2,3 },{ 0,0,0 },{ 0,1,1 },{ 1,2,2 },{ 0,0,-1 },{ 0,1,2 },{ -1,-1,-1 },{ 0,0,1 },{ -1,0,1 },{ -1,0,0 },{ 1,1,2 },{ 1,1,2 },
{ 0,-1,-1 },{ -1,-1,-2 },{ 0,1,1 },{ 0,-1,-2 },{ 1,1,1 },{ -1,-2,-2 },{ 0,0,1 } };
 
vector<int> vc[19] = { { 0,0,0 },{ 1,2,3 },{ 1,0,1 },{ 0,0,1 },{ 1,2,2 },{ 1,1,1 },{ 0,1,2 },{ 1, 2, 1 },
{ 1,1,1 },{ 1,1,2 },{ 0,1,0 },{ 0,1,1 },{ 1,1,2 },{ 0,1,1 },{ 1,1,2 },{ 1,1,1 } ,{ 0,1,2 } ,{ 0,0,1 } ,{ 1,2,2 } };
 
void calculate() {
    int cnt = 0;
    for (int con = 0; con < 19; con++) {
 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int Sum = m[i][j];
                bool isBreak = false;
 
                for (int k = 0; k < 3; k++) {
                    int nr = i + vr[con][k];
                    int nc = j + vc[con][k];
                    if (nr < 0 || nc < 0 || nr >= row || nc >= col) {
                        isBreak = true;
                        break;
                    }
                    Sum += m[nr][nc];
 
                }
                if (!isBreak)
                    if (Sum > Max) Max = Sum;
            }
        }
    }
 
}
int main(void) {
    cin >> row >> col;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
 
    calculate();
    cout << Max << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2003번: 수들의 합 2 (C++)  (0) 2019.08.29
백준 13458번: 시험 감독 (C++)  (0) 2019.08.29
백준 14503번: 로봇 청소기 (C++)  (0) 2019.08.28
백준 14888번: 연산자 끼워넣기 (C++)  (0) 2019.08.27
백준 11328번 Strfry (C++)  (0) 2019.08.25

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



초기 사다리의 정보를 입력받은 이후에, 사다리를 추가로 놓을 수 있는 곳들을 모두 찾아서 3개 이하로 사다리를 놓아보고, 문제에서 정해준 조건대로 i번에서 출발하면 i번 라인으로 도착할 수 있는지를 확인해주면 된다.




사다리를 모두 놓아보는 방법에는 여러가지가 있을 것 같은데, 본인은 먼저 사다리 하나를 놓을 수 있는 모든 경우를 찾아서 벡터에 담았다.



그리고 문제에서 3개 이하로만 확인하면 된다고 했기 때문에, 0개부터 3개까지 사다리를 놓아보고, i열에서 출발해서 i열로 도착할 수 있는지를 확인했다.



사다리를 놓을 수 있는 최솟값을 찾는 것이기 때문에, 중간에 어떤 경우라도 조건을 만족하면, 탐색을 멈추고 답을 출력한다.



사다리를 놓아볼 때는, 가령 (1,3) (1,4)에 놓아지는 사다리를 추가할 때는, 당연하게도 (1,4)에서 출발하는 사다리를 놓을 수 없기 때문에 이에 맞는 처리를 해주면 된다.


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
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
int col, m, row, map[31][11], st = 0;
bool isused[31][11], ansUpdate = false;
vector<pii> v;
int ans = -1;
 
void btk(int k, int num) {
    if (k == num) { //사다리의 개수
        
        bool suc = true; //답을 찾았는지
        for (int i = 1; i <= col; i++) {
            pii pos = { 1, i }; //출발 지점
            bool isFirst = true; //true면 가로로 이동, false면 세로로 이동
            while (pos.first <= row) {
                
                if (map[pos.first][pos.second] != 0) { //가로 사다리 만나면
                    if (isFirst == true) { //가로이동 할 차례
                        pos.second = map[pos.first][pos.second];
                        isFirst = false; //다음엔 세로 이동 하도록
                        
                    }
                    else { //세로로 이동할 차례
                        isFirst = true; //다음엔 가로로 이동하도록
                        pos.first++;
                        
                    }
                }
                else 
                    pos.first++; //가로 사다리가 없는 곳이면 아래로 이동
                
            }
            if (pos.second != i) { //출발점과 도착지점의 열값이 다르면 실패
                suc = false;
                break;
            }
        }
        if (suc) {
            ansUpdate = true;
            ans = num;
        }
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        int r = v[i].first; //r,c와 r,c+1이 사다리
        int c = v[i].second;
        if (!isused[r][c] && !isused[r][c + 1]) {
            isused[r][c] = true;
            isused[r][c + 1] = true;
            st = i;
            map[r][c] = c + 1; //r,c에서 사다리를 보면 r, c+1로 이동
            map[r][c + 1] = c; //위와 반대
            btk(k + 1, num);
            if (ansUpdate) return; //정답 찾으면 백트레킹 그만
            isused[r][c] = false;
            isused[r][c + 1] = false;
            map[r][c] = 0;
            map[r][c + 1] = 0;
        }
    }
}
int main(void) {
    cin >> col >> m >> row;
    for (int i = 0; i < m; i++) {
        int rw, st;
        cin >> rw >> st;
        map[rw][st] = st + 1;
        map[rw][st + 1] = st;
    }
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) 
            if (map[i][j] != 0)
                isused[i][j] = true; //처음부터 가로 사다리가 놓여진 곳
    
 
    //가로막대 놓을 수 있는 곳 찾아서 벡터에 시작점만 담기
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col - 1; j++) { //어짜피 가장 끝 열에는 사다리를 둘 수 없으니까 col -1
            if (!isused[i][j] && !isused[i][j + 1]) {
                isused[i][j] = true;
                isused[i][j + 1] = true;
                v.push_back({ i, j });
                isused[i][j] = false;
                isused[i][j + 1] = false;
            }
        }
    }
    
    
    for (int i = 0; i <= 3; i++) {
        if (ansUpdate) break; //최솟값 찾는 거니까 하나라도 찾으면 그만
        btk(0, i);
    }
    printf("%d", ans);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.24
백준 17140번: 이차원 배열과 연산 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20

+ Recent posts

티스토리툴바