티스토리 뷰
+) 추가! 다 풀고나서 바킹독님 강의를 보고 알게된건데, 스티커를 받자마자 바로 붙일 수 있으니까 굳이 배열에 저장할 필요 없이 스티커를 받고 바로 대보면 된다! 다음에 비슷한 문제가 있으면 이렇게 풀어봐야겠다.
https://www.acmicpc.net/problem/18808
18808번: 스티커 붙이기
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연
www.acmicpc.net
시뮬레이션 문제이다. 그냥 문제에 나온 그대로 구현하면 정답을 받는다. 물론 그대로 구현하는게 어렵다...
n*m 크기의 노트북에 r*c크기의 스티커 k개를 붙이는데, 붙이는 과정은 다음과 같다.
1. 배열의 가장 위, 그중에서 가장 왼쪽부터 가장 아래, 가장 오른쪽까지(배열의 [0][0]~[n-1][m-1]) 스티커를 입력받은 순서대로 대본다.
2. 스티커를 붙일 수 있으면 바로 붙이고, 붙일 수 없는 경우 1번으로 돌아가서 n-1,m-1까지 대본다.
3. 2번 과정이 끝나도 스티커를 붙일 수 없는 경우 90도 회전하여 다시 1,2번을 반복한다.
4. 270도 회전이 끝나도 스티커를 붙일 수 없다면 해당 스티커는 버린다.
이렇게 스티커 k개를 모두 붙여보고 나서, 노트북에 스티커가 붙어있는 칸의 개수를 출력하면 된다.
내가 볼 때 중요한 것은 스티커를 입력받은 순서대로 붙여야 한다는 것이다. 스티커를 모두 대본 다음 가장 많이 붙이는게 아니고, 먼저 들어온 스티커를 먼저 붙여야 한다.
노트북의 크기가 최대 40*40이고, 스티커의 크기는 최대 10*10, 스티커의 개수는 최대 100개이다.
스티커의 크기가 10*10인 스티커 100개를 40*40인 노트북에 모두 대본다고 할 때, 회전은 총 4번 하고 회전된 각각의 스티커를 모두 노트북의 [0][0]부터 [39][39]까지 대보아야 하므로, 총 연산 횟수는 다음과 같다.
총 연산 횟수가 6400만밖에 되지 않기 때문에 충분히 시간안에 들어올 수 있다고 생각해서 바로 코드 작성을 시작했다.
이 문제는 스티커를 회전하는 rotate 함수와 스티커를 붙이는 attach 함수 2개가 핵심이다.
1) rotate
|
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
|
vector <vector <int>> rotate(int k, int count, int t[MAX][MAX])
{
int row = stickersize[k].X, col = stickersize[k].Y;
int tmp[MAX][MAX];
for (int i = 0; i < MAX; i++)
fill(tmp[i], tmp[i] + MAX, -1);
for (int x = 0; x < count; x++)
{// tmp에 스티커를 90도 회전해서 채우기
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
tmp[j][row - 1 - i] = t[i][j];
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
t[i][j] = tmp[i][j];
// 한번 돌리고 나서 row와 col의 위치를 바꿔야 올바르게 회전함
swap(row, col);
}
vector <vector<int>> sticker;
vector <int> v;
// 벡터 v는 열이므로 열의 개수만큼 크기 맞추기
for (int i = 0; i < col; i++)
v.push_back(0);
// 벡터 sticker는 2차원 배열이므로 행의 개수만큼 v를 push
for (int i = 0; i < row; i++)
sticker.push_back(v);
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
sticker[i][j] = t[i][j];
return sticker;
}
|
cs |
먼저 k번째 스티커 t를 받아온 다음, 회전 횟수(count)만큼 회전한다. 이 때 한 번 회전하고 나면 행, 열의 위치를 swap하는게 중요하다. swap하지 않으면 배열의 인덱스가 엉망이 된다.
이후 2차원 벡터 sticker, 1차원 벡터 v를 선언해서 열의 개수 만큼 v의 크기를 맞춰주고, 행의 개수 만큼 sticker의 크기를 맞춰준다. 이후 sticker에 값을 복사하고 리턴하면 된다.
2) attach
|
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
|
bool attach(int k,int count)
{
int tsticker[MAX][MAX];
bool flag = false;
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
tsticker[i][j] = a[k][i][j];
vector<vector<int>> sticker;
sticker = rotate(k, count,tsticker);
// board 전체를 탐색
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// k번째 스티커의 행,열만큼 탐색
for (int x = 0; x < sticker.size(); x++)
{
for (int y = 0; y < sticker[x].size(); y++)
{
// OOB
if ((i + x) >= n || (j + y) >= m)
{
flag = true;
break;
}
// 스티커를 붙일 수 없는 경우
if (board[i + x][j + y] == A && sticker[x][y] == A)
{
flag = true;
break;
}
}
if (flag) break;
}
if (!flag)
{// flag = false면 붙일 수 있음
for (int x = 0; x < sticker.size(); x++)
{
for (int y = 0; y < sticker[x].size(); y++)
{
// board에 스티커 붙이기
if (sticker[x][y] == UA) continue;
board[i + x][j + y] = sticker[x][y];
}
}return true;
}
else
{
flag = false;
}
}
}
return false;
}
|
cs |
회전한 sticker를 받아온 다음 노트북의 [0][0]부터 [n-1][m-1]까지 반복문을 돌리면서 스티커를 붙일 수 있는지 확인하면 된다.
스티커가 노트북의 크기보다 크거나, 인덱스를 넘어가는 경우가 있을 수 있기 때문에 OOB를 체크해야 하고, 스티커를 붙일 수 없는 경우는 노트북의 해당 칸에 이미 스티커가 붙어있고, 스티커의 해당 칸의 값이 1인 경우이기 때문에 이런 경우 flag를 true로 설정해주고 반복문을 빠져나가면 된다.
만약 내부 2중 for문이 모두 돌아도 flag가 false라면 OOB나 스티커를 붙일 수 없는 경우가 존재하지 않는 것이므로
board에 스티커를 붙여주고 true를 리턴하면 된다.
만약 flag가 true인 상태로 끝난다면 false를 리턴해서 한바퀴 더 회전하면 된다.
아래는 전체 코드이다.
|
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*백준 18808번 스티커 붙이기 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 12
#define BMAX 42
#define X first
#define Y second
#define U -1
#define UA 0
#define A 1
int a[102][MAX][MAX], board[BMAX][BMAX];
int n, m, r, c, stickercount;
vector <pair<int, int>> stickersize; // 스티커의 각 row,col 크기를 저장하는 vector
// 스티커 회전 함수
vector <vector <int>> rotate(int k, int count, int t[MAX][MAX])
{
int row = stickersize[k].X, col = stickersize[k].Y;
int tmp[MAX][MAX];
for (int i = 0; i < MAX; i++)
fill(tmp[i], tmp[i] + MAX, -1);
for (int x = 0; x < count; x++)
{// tmp에 스티커를 90도 회전해서 채우기
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
tmp[j][row - 1 - i] = t[i][j];
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
t[i][j] = tmp[i][j];
// 한번 돌리고 나서 row와 col의 위치를 바꿔야 올바르게 회전함
swap(row, col);
}
vector <vector<int>> sticker;
vector <int> v;
// 벡터 v는 열이므로 열의 개수만큼 크기 맞추기
for (int i = 0; i < col; i++)
v.push_back(0);
// 벡터 sticker는 2차원 배열이므로 행의 개수만큼 v를 push
for (int i = 0; i < row; i++)
sticker.push_back(v);
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
sticker[i][j] = t[i][j];
return sticker;
}
void input()
{
for (int k = 0; k < 102; k++)
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
a[k][i][j] = U;
cin >> n >> m >> stickercount;
for (int z = 0; z < stickercount; z++)
{
cin >> r >> c;
stickersize.push_back({ r,c });
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> a[z][i][j];
}
}
}
}
bool attach(int k,int count)
{
int tsticker[MAX][MAX];
bool flag = false;
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
tsticker[i][j] = a[k][i][j];
vector<vector<int>> sticker;
sticker = rotate(k, count,tsticker);
// board 전체를 탐색
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// k번째 스티커의 행,열만큼 탐색
for (int x = 0; x < sticker.size(); x++)
{
for (int y = 0; y < sticker[x].size(); y++)
{
// OOB
if ((i + x) >= n || (j + y) >= m)
{
flag = true;
break;
}
// 스티커를 붙일 수 없는 경우
if (board[i + x][j + y] == A && sticker[x][y] == A)
{
flag = true;
break;
}
}
if (flag) break;
}
if (!flag)
{// flag = false면 붙일 수 있음
for (int x = 0; x < sticker.size(); x++)
{
for (int y = 0; y < sticker[x].size(); y++)
{
// board에 스티커 붙이기
if (sticker[x][y] == UA) continue;
board[i + x][j + y] = sticker[x][y];
}
}return true;
}
else
{
flag = false;
}
}
}
return false;
}
int solve()
{
int res = 0;
for (int i = 0; i < stickercount; i++)
{
for (int count = 0; count < 4; count++)
{
// 최대 270도 회전 ( 0 = 0(360)도, 1 = 90도, 2 = 180도, 3 = 270도
// 만약 attach의 값이 true라면 스티커를 붙인 경우이므로 break
if (attach(i, count))
break;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// 값이 1 = 스티커가 붙은 경우
if (board[i][j] == A) res++;
}
}
return res;
}
int main()
{
input();
cout << solve();
}
|
cs |
solve 함수에서 스티커의 개수만큼 반복문을 돌고, 또 내부에서 4번 반복문을 돌면서 attach가 true일 경우 break하고 다음 반복으로 넘어간다.
이후 마지막에 board[i][j] == A(1)이면 값을 더해서 리턴한다.
'PS > 백준' 카테고리의 다른 글
| (C++) [백준 11559번] Puyo Puyo (0) | 2022.12.12 |
|---|---|
| (C++) [백준 12100번] 2048(Easy) (0) | 2022.12.09 |
| (C++) [백준 6603번] 로또 (0) | 2022.08.26 |
| (C++) [백준 1074번] Z (0) | 2022.08.10 |
| (C++) [백준 11729번] 하노이 탑 이동 순서 (0) | 2022.08.08 |
- Total
- Today
- Yesterday
- 1251
- 상범 빌딩
- 3197
- 2493
- 9328
- 두 수의 합
- 6593
- 16920
- SWEA
- 2146
- 17071
- 파핑파핑 지뢰찾기
- 숨바꼭질 5
- 5427
- 1475
- 6603
- 16933
- 숨바꼭질 4
- PS
- 벽 부수고 이동하기 2
- 벽 부수고 이동하기 3
- 5397
- 구름톤챌린지
- 백준
- 3273
- BOJ
- 2583
- DX부문
- 3190번
- 확장 게임
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |