글 읽기 - 반례 혹은 알고리즘 검토좀 부탁드리겠습니다.

khj878 3년 전 0

예제 테스트케이스는 통과하였으나

반례를 찾기 힘들어 질문 올립니다.

프로그램 대략적인 구조는 가로축 긴변, 짧은변, 세로축 긴변, 짧은변을

res 배열에 넣어주는게 핵심입니다.

오타나 알고리즘상 에러 혹은 반례가 있다면 알려주시면 감사드리겠습니다.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <sstream>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;

//동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4
typedef struct Struct {
	int direction, length;
};

Struct S[6];
int cnt[4];
int res[4];//x큰변, y큰변, x작은변, y작은변
int K;

bool cmp(const Struct& s1, const Struct& s2) {
	if (s1.direction < s2.direction)
		return true;
	else {
		if (s1.direction == s2.direction)
			return s1.length < s2.length;
		return false;
	}
	return false;
}

//항상 짝수가(2) 2개의 방향에 2개씩 존재,
//항상 홀수가(1) 2개의 방향에 1개씩 존재

int main() 
{
	cin >> K;
	for (int i = 0; i < 6; i++) {
		cin >> S[i].direction >> S[i].length;
		cnt[S[i].direction - 1]++;
	}

	sort(S, S + 6, cmp);

	if (cnt[0] == 2) {
		int SUM = 0;
		for (int i = 0; i < 6; i++) {
			if (S[i].direction == 1)
				SUM += S[i].length;
		}
		res[0] = max(SUM, S[1].length);
		res[1] = min(SUM, min(S[0].length,
			S[1].length));
	}
	else {
		int SUM = 0;
		for (int i = 0; i < 6; i++) {
			if (S[i].direction == 2)
				SUM += S[i].length;
		}
		res[0] = max(SUM, S[0].length);
		res[1] = min(SUM, min(S[0].length,
			S[1].length));
	}

	if (cnt[2] == 2) {
		int SUM = 0;
		for (int i = 0; i < 6; i++) {
			if (S[i].direction == 3)
				SUM += S[i].length;
		}
		res[2] = max(SUM, S[3].length);
		res[3] = min(SUM, min(S[3].length,
			S[2].length));
	}
	else {
		int SUM = 0;
		for (int i = 0; i < 6; i++) {
			if (S[i].direction == 4)
				SUM += S[i].length;
		}
		res[2] = max(SUM, S[2].length);
		res[3] = min(SUM, min(S[3].length,
			S[2].length));
	}
	//for (int i = 0; i < 4; i++)
	//	cout << res[i] << endl;
	cout << K * (res[0] * res[2] -
		res[1] * res[3]);

	return 0;
}

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

문제

문제

출처

ICPC

반례 혹은 알고리즘 검토좀 부탁드리겠습니다.

khj878 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말