글 읽기 - 어디가 문제인지 모르겠습니다 ㅜㅜ

sminhyuck 4년 전 0

격벽을 따라서만 스티커 부착이 가능하다 했으니, 격벽을 따라서만 탐색을 하도록 했습니다.

테스트 케이스는 모두 맞았고, 어디서 놓쳤는지 못찾겠습니다 ㅜㅜ

//https://www.acmicpc.net/problem/16937
// 2019.08.02 14:58~
#include <iostream>
#include <algorithm>
using namespace std;

struct STICKER {
	int R, C;
};
STICKER S[200];	// 넓이 기준으로 내림차순, 내림차순 된 스티커에서 90회전(R과 C가 바뀜)
int H, W, N;	// 높이, 가로, 스티커 수
int MAX;
int H1, W1, H2, W2;

bool comp(const STICKER& a, STICKER& b) {
	if (a.R * a.C > b.R * b.C) return true;
	else return false;
}


void init() {
	H1 = -1; W1 = -1; H2 = -1; W2 = -1; MAX = 0;
	cin >> H >> W >> N;
	
	for (int i = 0; i < N; i++) {
		int r, c;
		cin >> r >> c;
		S[i].R = r; S[i].C = c;
	}
	for (int i = 0; i < N; i++) {
		S[i + N].R = S[i].C;
		S[i + N].C = S[i].R;
	}
	sort(S, S + 2*N, comp);
	N = 2 * N;

}

// 해당 스티커를 붙일 공간이 있는지 확인
bool check(STICKER s,int r, int c, int t) {
	
	if (r < 0 || c < 0) return false;
	// 스티커를 부착했을때 모눈종이를 벗어날 경우
	if (r + s.R  > H || c + s.C > W) return false;
	// 기존 붙은 스티커에 붙힐 스티커가 겹칠 경우
	if (t == 1) {
		if (((H1 <= r + s.R - 1 && H2 >= r + s.R - 1) && (W1 <= c && W2 >= c)) || ((H1 <= r && H2 >= r) && (W1 <= c + s.C -1 && W2 >= c + s.C - 1))) return false;
		if (((H1 <= r && H2 >= r) && (W1 <= c && W2 >= c)) || ((H1 <= r + s.R - 1 && H2 >= r + s.R - 1) && (W1 <= c + s.C -1 && W2 >= c + s.C - 1))) return false;
	}
	
	return true;
}

void DFS(int t, int sum, int next) {
	if (t >= 2) {
		if (MAX < sum) MAX = sum;
		return;
	}

	for (int i = next; i < N; i++) {
        if (t == 0 && MAX >= S[i].R * S[i].C * 2) return;
		if (t == 1 && MAX >= sum + S[i].R * S[i].C) return;
		// 왼쪽 격벽
		for (int h = 0; h <= H - S[i].R; h++) {
			if (t == 0) {
				H1 = h; W1 = 0; 
				H2 = h + S[i].R - 1; W2 = S[i].C - 1;
			}
			if (check(S[i], h, 0,t)) DFS(t + 1, sum + S[i].R * S[i].C, i + 1);
		}
        if (t == 0 && MAX >= S[i].R * S[i].C * 2) return;
		if (t == 1 && MAX >= sum + S[i].R * S[i].C) return;
		// 위 격벽
		for (int w = 0; w <= W - S[i].C; w++) {
			if (t == 0) {
				H1 = 0; W1 = w;
				H2 =  S[i].R - 1; W2 = w + S[i].C - 1;
			}
			if (check(S[i], 0, w,t)) DFS(t + 1, sum + S[i].R * S[i].C, i + 1);
		}
        if (t == 0 && MAX >= S[i].R * S[i].C * 2) return;
		if (t == 1 && MAX >= sum + S[i].R * S[i].C) return;
		// 오른쪽 격벽
		for (int h = 0; h <= H - S[i].R; h++) {
			if (t == 0) {
				H1 = h; W1 = W-S[i].C;
				H2 = h + S[i].R - 1; W2 = W - 1;
			}
			if (check(S[i], h, W-S[i].C,t)) DFS(t + 1, sum + S[i].R * S[i].C, i + 1);
		}
        if (t == 0 && MAX >= S[i].R * S[i].C * 2) return;
		if (t == 1 && MAX >= sum + S[i].R * S[i].C) return;
		// 아랫쪽 격벽
		for (int w = 0; w <= W - S[i].C; w++) {
			if (t == 0) {
				H1 = H-S[i].R; W1 = w;
				H2 = H-1; W2 = w + S[i].C - 1;
			}
			if (check(S[i], H-S[i].R, w,t)) DFS(t + 1, sum + S[i].R * S[i].C, i + 1);
		}
	}
}

int main() {
	init();
	DFS(0, 0, 0);
	cout << MAX << endl;
}

kyo20111 4년 전 1

디버깅은 어려워보여 팁 하나만 놓고 가겠습니다.

스티커 2개는 대각선 끝 꼭짓점에 놓는것이 이득이라고 생각하고 풀어보세요.

sminhyuck 4년 전 0

말씀해주신부분 참고해서 첫번쨰 스티커는 왼쪽 위, 두번째 스티커는 오른쪽 아래에 부착하도록해서 작성했습니다.

테스트케이스는 잘 돌아가나 여전히 바로 틀렸습니다가 뜨네요 ㅜㅜ

로직에서 잘못된 부분이 있을까요?

스티커 정보인 벡터 S 안에는 넓이가 큰 순으로 정렬되어있기에, 가장 먼저 답을 찾았을 시 최대값이 되도록 하였습니다.

스티커 부착 가능 확인은 모눈종이를 벗어나는 크기인지 우선 확인.

이전에 부착한 스티커와 범위가 겹치는지 확인하여 판단하도록 했습니다.

//https://www.acmicpc.net/problem/16937
// 2019.08.02 14:58~
#include <iostream>
#include <algorithm>
using namespace std;

struct STICKER {
	int R, C;
};
STICKER S[200];	// 넓이 기준으로 내림차순, 내림차순 된 스티커에서 90회전(R과 C가 바뀜)
int H, W, N;	// 높이, 가로, 스티커 수
int MAX;
int H1, W1, H2, W2;	// 스티커를 붙인 범위 - R = 1, C = 1 인 스티커면 H1, H2 =0, W1,W2 = 0이 됨
bool FIND;

bool comp(const STICKER& a, STICKER& b) {
	if (a.R * a.C > b.R * b.C) return true;
	else return false;
}


void init() {
	FIND = false;
	H1 = 0; W1 = 0;
	cin >> H >> W >> N;

	for (int i = 0; i < N; i++) {
		int r, c;
		cin >> r >> c;
		S[i].R = r; S[i].C = c;
	}
	for (int i = 0; i < N; i++) {
		S[i + N].R = S[i].C;
		S[i + N].C = S[i].R;
	}
	sort(S, S + 2 * N, comp);
	N = 2 * N;
}

// 해당 스티커를 붙일 공간이 있는지 확인
bool check(STICKER s, int r, int c, int t) {
	// 스티커를 부착했을때 모눈종이를 벗어날 경우
	if (r < 0 || c < 0) return false;
	if (r + s.R > H || c + s.C > W) return false;
	
	// 스티커가 붙은 네 모서리인 H1,W1,H2,W2 안 에 새로 부착하는 위치가 겹치는지 확인
	if (t==1 && (H1 <= r && H2 >= r) && (W1 <= c && W2 >= c)) return false;
	
	return true;
}

void DFS(int t, int sum, int next) {
	if (t == 2) {
		if (MAX < sum) MAX = sum;
		FIND = true;
		return;
	}
	if (FIND) return;

	for (int i = next; i < N; i++) {
		if (t == 0) {
			if (check(S[i], 0, 0, 0)) {	// 왼쪽 아래에 스티커 부착
				H2 = S[i].R - 1; W2 = S[i].C - 1;	
				DFS(t + 1, S[i].R * S[i].C, i);
			}
		}
		else {
			if (check(S[i], H - S[i].R, W - S[i].C, 1)) {	// 오른쪽 아래에 스티커 부착
				DFS(t + 1, sum + S[i].R * S[i].C, i);
			}
		}
	}
}

int main() {
	init();
	DFS(0, 0, 0);
	cout << MAX << endl;
}

kyo20111 4년 전 1

각 스티커는 1번씩만 사용할 수 있습니다.

input:
10 10
2
5 5
10 10
    
output:
0

kyo20111 4년 전 1

저 부분을 고쳐도 이러한 반례가 나올수도 있겠네요.(넓이순 정렬시)

input:
4 4
4
3 4
1 1
2 4
4 2

output:
16

sminhyuck 4년 전 1

중복 사용하는 부분을 놓쳤었네요!

조언해주신 덕분에 문제 풀 수 있었습니다.

정말 감사합니다 ㅜㅜ

즐거운 주말 되세요 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 문제인지 모르겠습니다 ㅜㅜ

sminhyuck 4년 전 0

kyo20111 4년 전 1

sminhyuck 4년 전 0

kyo20111 4년 전 1

kyo20111 4년 전 1

sminhyuck 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말