궤도
[백준] 14391번 : 종이 조각 본문
문제
풀이
솔직히 어려워서 힌트를 봤다. 난 절대 떠올리지 못했을 방법이었다.
일단 이 문제는 비트마스크이다. 2차원 배열에 어떻게 비트마스크를? 싶을 수도 있겠지만
0~(1<<(N*M))을 하면 된다. 이걸 다시 2차원에 적용하는게 귀찮지만...
아무튼 0으로 표시한건 가로 블록으로 취급할 것이고 1로 표시한건 세로 블록으로 취급할 것이다.
000
000
이라면 길이 3의 가로 블록이 2개 있는 것이고
010
111
이라면 길이 1의 가로 블록 2개와 세로 블록 1개, 그리고 길이 3의 세로블록 1개가 있는 것이다.
소스코드
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int matrix[4][4], N, M;
int calc(int num) {
int result = 0;
bool checked[16] = {0};
for (int i = 0; i < N * M; i++) {
if (!checked[i]) { //방문 여부 확인
if (((1 << i) & num) == 0) { //0이면 가로 블럭
checked[i] = true;
string horizontal = to_string(matrix[i / M][i % M]);
for (int j = i + 1; j % M != 0; j++) { //가로 탐색
if (((1 << j) & num) != 0) //세로 블럭이면 break
break;
checked[j] = true;
horizontal += to_string(matrix[j / M][j % M]);
}
result += stoi(horizontal); //결과에 더함
} else if (((1 << i) & num) != 0) { //1이면 세로 블럭
checked[i] = true;
string vertical = to_string(matrix[i / M][i % M]);
for (int j = i + M; j / M < N; j += M) { //세로 탐색
if (((1 << j) & num) == 0) //가로 블럭이면 break
break;
checked[j] = true;
vertical += to_string(matrix[j / M][j % M]);
}
result += stoi(vertical); //결과에 더함
}
}
}
return result;
}
int main() {
string tmp;
int max_sum = 0;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> tmp;
for (int j = 0; j < M; j++)
matrix[i][j] = tmp[j] - '0';
}
for (int i = 0; i < (1 << (N * M)); i++) //N=2, M=2일 때 0000부터 1111까지
max_sum = max(max_sum, calc(i));
cout << max_sum;
}전체 소스코드다.
for (int i = 0; i < N; i++) {
cin >> tmp;
for (int j = 0; j < M; j++)
matrix[i][j] = tmp[j] - '0';
}
for (int i = 0; i < (1 << (N * M)); i++) //N=2, M=2일 때 0000부터 1111까지
max_sum = max(max_sum, calc(i));입력을 처리하고 i=0부터 i=(1<<(N*M)-1일 때까지 반복문을 돌며 calc 함수로 계산을 한다.
여기까진 쉽다.
int calc(int num) {
int result = 0;
bool checked[16] = {0};
for (int i = 0; i < N * M; i++) {
if (!checked[i]) { //방문 여부 확인
if (((1 << i) & num) == 0) { //0이면 가로 블럭
checked[i] = true;
string horizontal = to_string(matrix[i / M][i % M]);
for (int j = i + 1; j % M != 0; j++) { //가로 탐색
if (((1 << j) & num) != 0) //세로 블럭이면 break
break;
checked[j] = true;
horizontal += to_string(matrix[j / M][j % M]);
}
result += stoi(horizontal); //결과에 더함
} else if (((1 << i) & num) != 0) { //1이면 세로 블럭
checked[i] = true;
string vertical = to_string(matrix[i / M][i % M]);
for (int j = i + M; j / M < N; j += M) { //세로 탐색
if (((1 << j) & num) == 0) //가로 블럭이면 break
break;
checked[j] = true;
vertical += to_string(matrix[j / M][j % M]);
}
result += stoi(vertical); //결과에 더함
}
}
}
return result;
}종이의 경계에 따라 계산하는 calc 함수이다.
일단 최종 합을 저장할 result와 각 칸의 방문여부를 체크할 checked 배열이다.
배열의 모든 원소를 탐색할 것이기 때문에 0부터 N*M-1까지 반복문을 돈다.
i에 대해 체크여부를 확인하고 체크된 칸이 아니라면 가로 세로 블럭 여부를 확인한다.
if (((1 << i) & num) == 0) { //0이면 가로 블럭
checked[i] = true;
string horizontal = to_string(matrix[i / M][i % M]);
for (int j = i + 1; j % M != 0; j++) { //가로 탐색
if (((1 << j) & num) != 0) //세로 블럭이면 break
break;
checked[j] = true;
horizontal += to_string(matrix[j / M][j % M]);
}
result += stoi(horizontal); //결과에 더함만약 (1<<i)&num이 0이라면 그니까 i번째 비트가 0이라면 이건 가로 블럭이란 뜻이다.
000
000
에 대해 index로 바꿔 작성하면
012
345
가 된다.
index를 M(=3)으로 나누어 떨어질 때, 다음 열로 넘어갔다는 뜻이니까 그 전까지 가로 블록 여부를 확인한다.
나중에 stoi로 손쉽게 바꾸기 위해 string 변수에 숫자를 쌓아나간다.
만약 범위가 넘어가거나, 세로블럭을 만나 반복문이 종료된다면 stoi로 string을 정수로 바꿔 result에 더한다.
} else if (((1 << i) & num) != 0) { //1이면 세로 블럭
checked[i] = true;
string vertical = to_string(matrix[i / M][i % M]);
for (int j = i + M; j / M < N; j += M) { //세로 탐색
if (((1 << j) & num) == 0) //가로 블럭이면 break
break;
checked[j] = true;
vertical += to_string(matrix[j / M][j % M]);
}
result += stoi(vertical); //결과에 더함
}한편 (1<<i)&num이 0이 아니라면 i번째 비트가 1이라는 뜻이고 세로 블럭이란 뜻이다.
다시 아까 index를 가져오면
012
345
인데
아래로 내려갈때마다 각 index에 M(=3)이 더해지는 것을 볼 수 있다. 그러므로 j+=M이 증가 조건이 된다.
만약 index를 M으로 나눈 몫이 N보다 크다면 범위를 벗어난 것이기 때문에 j/M<N인 동안에만 반복한다.
아까와 마찬가지로 반복문을 빠져나오면 그 결과를 result에 더해준다.
