반응형

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

 

17136번: 색종이 붙이기

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 사용한 종이의 개수를 저장할 배열을 생성합니다.

 

2. 덮어야 하는 좌표라면 종이의 크기가 1부터 5까지 돌아가면서 덮을 수 있는 종이가 있다면 덮습니다.

 

3. 마지막 좌표까지 갔을 때 모두 덮여 있다면 최솟값을 저장합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int arr[10][10];
int cnt[6];
int ans = 987654321;
int cnt1;
 
void reset(int y, int x, int n)        //덮었던 색종이를 제거
{
    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
            arr[i][j] = 1;
        }
    }
}
 
void change(int y, int x, int n)    //색종이 덮기
{
    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
            arr[i][j] = 0;
        }
    }
}
 
bool stick(int y, int x, int n)    //색종이를 붙일 수 있는지 없는지 체크
{
    if (y + n > 10 || x + n > 10) return false;
    for (int i = y; i < y+n; i++) {
        for (int j = x; j < x+n; j++) {
            if (arr[i][j] == 0) {
                return false;
            }
        }
    }
 
    return true;
}
 
bool check()    //색종이가 다 덮였는지 체크
{
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (arr[i][j] == 1) {
                return false;
            }
        }
    }
 
    return true;
}
 
void dfs(int level, int cur)
{
    if (cur == 100 && check()) {    //마지막 좌표에 도착 및 모두 덮였을 때
        ans = min(ans,level);
        return;
    }
    if (cur == 100) return;
 
    if (arr[cur / 10][cur % 10] == 0) dfs(level, cur + 1);    //덮을 필요 없는 좌표
 
    for (int i = 5; i >= 1; i--) {
        if (cnt[i] <= 4) {
            if (arr[cur / 10][cur % 10] == 1) {    //덮어야하는 좌표
                if (stick(cur / 10, cur % 10, i)) {
                    cnt[i]++;
                    change(cur / 10, cur % 10, i);
                    dfs(level + 1, cur + 1);
                    reset(cur / 10, cur % 10, i);
                    cnt[i]--;
                }
            }
        }
    }
}
 
int main()
{
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dfs(0, 0);
 
    if (ans != 987654321) {
        printf("%d", ans);
    }
    else {
        printf("%d", -1);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17406번 - 배열 돌리기 4 (C++)  (0) 2022.10.08
[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 23290번 - 마법사 상어와 복제 (C++)  (0) 2022.10.05
[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03

+ Recent posts

티스토리툴바