[BOJ] 17136 : 색종이 붙이기
풀이
백트래킹
삼성19-4월 상시SW테스트 2번문제.
시험장에서 시험쳤다. 전부1인경우 오래걸리길래
조합을 찾다가 정답을 하나라도 찾으면 바로 종료를 시키게 했다.
그러니 테케는 다맞았다. 감기때문에 몸이 너무 안좋아서 그냥 제출하고
2시간만에 나왔다.
복원문제를 풀면서 예외가 있다는것을 알았따 너무 슬프다 ㅠㅠ
‘정답을 찾은경우’ 바로 종료를 하는게 아니라
정답을 하나이상 찾은경우 정답보다 개수가 큰수는 커팅하면 된다.
나는 일부로 블록이 큰것부터 들어갈수있도록 짯기때문에
첫번째 정답부터 개수가 상당히 작다. 그래서 대부분이 이 조건에서 커팅이된다.
그리고 시험장에서 떠올리고는 정말 기뻤던 조건은
1의 개수를 더한다음에 블록조합의 크기의 합이 1의 개수의 합과 같은지 확인하는 코드이다.
시험전에 한번 더 보기위해 주석 처리를 상세하게 해두었다.
코드
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int n = 10;
int arr[n][n];
int backup[n][n];
//1의 개수의 합
int allSum = 0;
//5,4,3,2,1개 색종이의 각각 사용할 숫자
vector<int> v;
int ans = -1;
int flag = 0;
//색종이 붙이기 함수
void fix(int t, int cnt) {
//답이 나온경우에 개수는 동일하므로 더 볼필요없다.
if (flag)
return;
//가능한 경우를 찾음
if (t == 0) {
flag = 1;
return;
}
//v[size]를 다붙였음.
if (v[5 - t] == cnt)
fix(t - 1, 0);
for (int i = 0; i <= n - t; i++) {
for (int j = 0; j <= n - t; j++) {
if (arr[i][j] == 1) {
int ok = 1;
for (int k = i; k < i + t; k++) {
for (int l = j; l < j + t; l++) {
if (arr[k][l] == 0) {
ok = 0;
break;
}
}
if (ok == 0)
break;
}
if (ok) {
for (int k = i; k < i + t; k++) {
for (int l = j; l < j + t; l++) {
arr[k][l] = 0;
}
}
fix(t, cnt + 1);
for (int k = i; k < i + t; k++) {
for (int l = j; l < j + t; l++) {
arr[k][l] = 1;
}
}
}
}
}
}
}
void go(int cnt) {
if (cnt == 5) {
//sum:블록 크기의 합
int sum = 0;
//numsum:블록의 개수
int numSum = 0;
for (int i = 0; i < 5; i++) {
sum += v[i] * (5 - i) * (5 - i);
numSum += v[i];
}
//조합으로 만든 블록들의 크기의 합이 allSum과 같을때만 확인하면된다.
if (sum != allSum)
return;
//****이부분을 안해서 틀렸었음 ㅠ
//정답을 하나이상 찾은경우, 정답보다 개수가 크면 볼필요없다
if (ans != -1) {
if (ans <= numSum)
return;
}
fix(5, 0);
//정답을 찾은경우
if (flag) {
flag = 0;
ans = numSum;
}
//fix함수에서 정답을 찾은경우 return했기때문에 롤백한다.
memcpy(arr, backup, sizeof(arr));
return;
}
//5부터 0까지 개수 조합을 짠다.
for (int i = 5; i >= 0; i--) {
v.push_back(i);
go(cnt + 1);
v.pop_back();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
backup[i][j] = arr[i][j];
if (arr[i][j] == 1) {
allSum++;
}
}
}
go(0);
cout << ans;
return 0;
}
Written on April 8, 2019