https://www.acmicpc.net/problem/14391
14391번: 종이 조각
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다. 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인
www.acmicpc.net
모든 칸(숫자)에 대해서 가로로 자를 경우를 1, 세로로 자를 경우를 0으로 놓고 비트 마스크를 사용하면 모든 경우를 빠르게 계산해줄 수 있다.
먼저 모든 경우를 위해 반복문을 0부터 1 << (n*m) 까지로 해준다.
n=2 , m=3
123
312
위와 같은 예를 들면,
000000부터 111111까지의 모든 경우를 구하는데, 각 행을 한 줄로 합쳐줘서 123312로 보고 계산하면 된다.
001100이라고 치면 3,3만 세로로 자르고 나머지는 가로로 자르는 경우이다.
각 경우마다 합을 구해서 최댓값과 비교해주면 된다.
각 경우에서는 가로 종이조각과 세로 종이조각의 수들을 구하여 합을 구해주면 된다.
먼저 한 줄로 보고 계산해줘야 하므로 k = i*m +j로 설정했다.
위의 예제에서 1행 2열의 '1'의 index는 k=4가 된다.
이런 식으로 1 << k와 모든 경우의 수를 해줄 b를 & 연산하여 각 k번째 자리에 1이 있는지 1이 없는지 구해주면 된다.
자리에 1이 있는 경우 세로이고 0이 있는 경우는 가로이다.
가로인 애들을 먼저 구해주면
각 행에서만 붙어 있는 숫자만이 하나의 숫자가 될 수 있으므로 한 행이 끝나면 sum에 더해주고 새로 숫자를 구해준다.
같은 행에서 숫자를 합치던 중에 세로인 애가 나와도 sum에 더해주면 된다. 그리고 현재 숫자를 나타내는 변수는 0으로 해주고 새로 만들어야 한다.
숫자를 합치는 방법은 (이전 숫자*10 + 현재 숫자)를 해주면 된다.
예를 들어 기존에 2였다면 2*10+3을 해줘서 23을 만들 수 있다.
세로인 애들도 마찬가지로 구해주면 된다. 대신 한 열의 행을 먼저 봐서 세로로 숫자를 만들어 주도록 하면 된다.
세로는 해당 자리에 1이 있는 경우로 &연산 결과가 (001000) 이런 식으로 나올 것이다. 즉 0이 아닌 값이면 세로 숫자에 더해준다. 가로인 경우와 비슷하게 세로에서는 한 열이 끝나면 sum에 더해주고 새로 숫자를 만들어줘야 한다. 열 중간에 가로가 나오는 경우도 마찬가지이다.
|
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
|
#include <iostream>
#include <string>
using namespace std;
int n, m;
int paper[4][4];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < m; j++) {
paper[i][j] = s[j] - '0';
}
}
int ans = 0;
//모든 경우 구한다.
//0인 곳은 가로, 1인 곳은 세로
for (int b = 0; b < (1 << (n*m)); b++) {
int sum = 0;
//가로모양으로 자른 애들 계산
for (int i = 0; i < n; i++) {
int now = 0;
for (int j = 0; j < m; j++) {
//정사각형 종이 조각을 한줄로 이어 붙였을 때의 인덱스
int k = i*m + j;
//k번째 자리값이 0이다(가로로 자를거다)
if ((b & (1 << k)) == 0) {
now = now * 10 + paper[i][j];
}
else { //1인 경우(세로인 경우) 앞에까지 만들어진 조각을 sum에 더해준다.
sum += now;
now = 0;
}
}
//한 행이 끝났으면 만들어진 숫자 sum에 더해준다.
sum += now;
}
//세로 모양으로 자른 애들 계산
for (int j = 0; j < m; j++) {
int now = 0;
for (int i = 0; i < n; i++) {
//정사각형 종이 조각을 한줄로 이어 붙였을 때의 인덱스
int k = i*m + j;
//세로인 경우에 숫자를 만들어준다.
if ((b & (1 << k)) != 0) {
now = now * 10 + paper[i][j];
}
else {
sum += now;
now = 0;
}
}
sum += now;
}
//최댓값과 비교
if (ans < sum) ans = sum;
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2748. 피보나치 수 2 (0) | 2019.07.15 |
|---|---|
| [BOJ] 14889. 스타트와 링크(비트마스크 풀이) (0) | 2019.07.11 |
| [BOJ] 1182. 부분수열의 합 (0) | 2019.07.11 |
| [BOJ] 11723. 집합 (0) | 2019.07.11 |
| [BOJ] 1987. 알파벳 (0) | 2019.07.11 |