ACM 2002 문제 D 줄다리기 풀이
Track 0 (Previous)/Major : CE 2010. 2. 4. 22:31
문제입니다.
정말 유난히 고생했던 문제였습니다.
겉보기엔 쉬워 보입니다만, 간단히 오름차순 혹은 내림차순으로 정렬 후
차이가 적은 쌍을 찾아 묶어가는 방식으로 진행하게 되면 위의 Sample Input 에 대해서는
결과가 올바로 나옵니다만, 치명적인 함정이 있습니다.
간단한 예를 들어 5명일 경우 1:4 의 팀 구성에 대해 밸런스가 맞을 경우가 있습니다.
꽤나 극단적인 경우입니다만, 인원 수가 늘어날 수록 팀간의 인원 사이의 차이값 또한 커질 가능성이
있음을 말합니다. 곧, 이 알고리즘으로는 1:4 의 경우에 대해 해결할 수 없습니다.
(5명의 인원이 각기 40, 41, 42, 43, 158kg 일 경우 x >= 2 에 대해 1:4 조합이 모두 성립됩니다.)
이 각기의 조합에 대해 대체 무슨 수로 찾아내느냐를 한참동안 고민했습니다.
재귀 호출 방법을 통해 각각의 조합을 유도할 것인가... 대책 없죠. -_-;
그리고 오늘 불현듯 떠오른 방법으로 구현했습니다. 아이디어 짜내는데 시간이 오래 걸렸지,
컴파일은 한방에 했네요. 위의 어떤 경우라도 답을 구해냅니다만, 브루트포스 방법으로 답을
구해내기 때문에 효율성에 있어서는 합리적이라 보기 힘듭니다. 물론, 어떤 경우가 해당할 것인지
직관적으로 구분해내기 힘들지만, 이 경우만큼은 해당하지 않을 것이다... 는 구분할 수 있으니까요.
코드입니다.
실제 전공과 관련된 내용은 안 올리려 했는데 이 문제의 해결방안을 도저히 모를 때,
검색한 자료 전부 위의 찾아내지 못하는 결점을 그대로 반영했더군요;
혹시라도 고민하시는 분이 계실까 싶어 잊기 쉬운 점에 대해 지적하고, 코드를 포스팅합니다.
문제의 해결 방안에 대해서는 포스트에 언급하지 않고 코드를 보면 이해할 수 있는데,
되도록 그 점은 각자 구현해보시는 게 좋겠네요. 문제 인식만 된다면 얼마든;;
정말 유난히 고생했던 문제였습니다.
겉보기엔 쉬워 보입니다만, 간단히 오름차순 혹은 내림차순으로 정렬 후
차이가 적은 쌍을 찾아 묶어가는 방식으로 진행하게 되면 위의 Sample Input 에 대해서는
결과가 올바로 나옵니다만, 치명적인 함정이 있습니다.
간단한 예를 들어 5명일 경우 1:4 의 팀 구성에 대해 밸런스가 맞을 경우가 있습니다.
꽤나 극단적인 경우입니다만, 인원 수가 늘어날 수록 팀간의 인원 사이의 차이값 또한 커질 가능성이
있음을 말합니다. 곧, 이 알고리즘으로는 1:4 의 경우에 대해 해결할 수 없습니다.
(5명의 인원이 각기 40, 41, 42, 43, 158kg 일 경우 x >= 2 에 대해 1:4 조합이 모두 성립됩니다.)
이 각기의 조합에 대해 대체 무슨 수로 찾아내느냐를 한참동안 고민했습니다.
재귀 호출 방법을 통해 각각의 조합을 유도할 것인가... 대책 없죠. -_-;
그리고 오늘 불현듯 떠오른 방법으로 구현했습니다. 아이디어 짜내는데 시간이 오래 걸렸지,
컴파일은 한방에 했네요. 위의 어떤 경우라도 답을 구해냅니다만, 브루트포스 방법으로 답을
구해내기 때문에 효율성에 있어서는 합리적이라 보기 힘듭니다. 물론, 어떤 경우가 해당할 것인지
직관적으로 구분해내기 힘들지만, 이 경우만큼은 해당하지 않을 것이다... 는 구분할 수 있으니까요.
코드입니다.
/*=================================================
* 파일명 : main.cpp
* 작성자 : loopin (adelbera@empal.com)
* 작성일 : 2010.02.04
* 기 타 : 제 2 회 대학생 프로그래밍 온라인대회
문제 D '줄다리기' 풀이
=================================================*/
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <algorithm>
using std::fill;
using std::swap;
#include <cmath>
/* 변수 설명
results : 결과를 저장할 bool 배열의 포인터 변수
reftab : 두 팀의 분배 상황을 조합할 bool 배열의 포인터 변수
rept : 결과를 저장할 bool 배열의 위치 표현 변수
n : 문제에서의 n, 인원 수
x : 문제에서의 x, 최대 전력 차이량
lvcnt : 분배 상황에 대해 조합한 경우를 카운트 하는 변수
members : 사람들의 체중이 저장될 int 배열의 포인터 변수
*/
bool *results, *reftab;
int rept = 0, n = 0, x = 0, lvcnt = 0;
int *members;
// 다음 조합을 찾기 위한 함수
bool next_level()
{
int i = 0;
// carry 방식
while(i < n)
if(reftab[i]) reftab[i++] = false;
else
{
reftab[i] = true;
break;
}
if(++lvcnt < pow(2,n)-1) return true;
else return false;
}
// 결과를 출력할 목적의 함수
void output()
{
for(int i=0;i<rept;i++)
if(results[i]) cout << "YES" << endl;
else cout << "NO" << endl;
}
// YES, NO 판단을 위한 작업 함수
void process()
{
//몸무게 내림차순 정렬
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(members[i] < members[j])
swap(members[i], members[j]);
//비교를 위해 int 배열(2) 선언
int comp[2];
//다음 조합으로 변경하고 이 조합이 유효하다면 작업 내용 실행
while(next_level())
{
comp[0] = comp[1] = 0;
for(int i=0;i<n;i++)
if(reftab[i]) comp[1] += members[i];
else comp[0] += members[i];
//값의 차이가 x 값 이하일 때
if(abs(comp[1] - comp[0]) <= x)
{
results[rept] = true;
break;
}
}
rept++;
}
// 입력 목적의 함수
void input()
{
cin >> n >> x;
//범위 예외 처리
if(n < 4) n = 4;
else if(n > 30) n = 30;
if(x < 0) x = 0;
members = new int [n];
reftab = new bool [n];
fill(reftab, reftab+n, false);
for(int i=0;i<n;i++)
{
cin >> members[i];
if(members[i] < 40) members[i] = 40;
else if(members[i] > 160) members[i] = 160;
}
//계산을 위한 process 함수 호출
process();
delete [] members;
delete [] reftab;
}
int main()
{
//테스트 케이스 입력
int t;
cin >> t;
//범위 관련 예외 처리
if(t < 0) t = 1;
else if(t > 10) t = 10;
results = new bool [t];
fill(results, results+t, false);
while(t--) input();
output();
delete [] results;
return 0;
}
* 파일명 : main.cpp
* 작성자 : loopin (adelbera@empal.com)
* 작성일 : 2010.02.04
* 기 타 : 제 2 회 대학생 프로그래밍 온라인대회
문제 D '줄다리기' 풀이
=================================================*/
#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <algorithm>
using std::fill;
using std::swap;
#include <cmath>
/* 변수 설명
results : 결과를 저장할 bool 배열의 포인터 변수
reftab : 두 팀의 분배 상황을 조합할 bool 배열의 포인터 변수
rept : 결과를 저장할 bool 배열의 위치 표현 변수
n : 문제에서의 n, 인원 수
x : 문제에서의 x, 최대 전력 차이량
lvcnt : 분배 상황에 대해 조합한 경우를 카운트 하는 변수
members : 사람들의 체중이 저장될 int 배열의 포인터 변수
*/
bool *results, *reftab;
int rept = 0, n = 0, x = 0, lvcnt = 0;
int *members;
// 다음 조합을 찾기 위한 함수
bool next_level()
{
int i = 0;
// carry 방식
while(i < n)
if(reftab[i]) reftab[i++] = false;
else
{
reftab[i] = true;
break;
}
if(++lvcnt < pow(2,n)-1) return true;
else return false;
}
// 결과를 출력할 목적의 함수
void output()
{
for(int i=0;i<rept;i++)
if(results[i]) cout << "YES" << endl;
else cout << "NO" << endl;
}
// YES, NO 판단을 위한 작업 함수
void process()
{
//몸무게 내림차순 정렬
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(members[i] < members[j])
swap(members[i], members[j]);
//비교를 위해 int 배열(2) 선언
int comp[2];
//다음 조합으로 변경하고 이 조합이 유효하다면 작업 내용 실행
while(next_level())
{
comp[0] = comp[1] = 0;
for(int i=0;i<n;i++)
if(reftab[i]) comp[1] += members[i];
else comp[0] += members[i];
//값의 차이가 x 값 이하일 때
if(abs(comp[1] - comp[0]) <= x)
{
results[rept] = true;
break;
}
}
rept++;
}
// 입력 목적의 함수
void input()
{
cin >> n >> x;
//범위 예외 처리
if(n < 4) n = 4;
else if(n > 30) n = 30;
if(x < 0) x = 0;
members = new int [n];
reftab = new bool [n];
fill(reftab, reftab+n, false);
for(int i=0;i<n;i++)
{
cin >> members[i];
if(members[i] < 40) members[i] = 40;
else if(members[i] > 160) members[i] = 160;
}
//계산을 위한 process 함수 호출
process();
delete [] members;
delete [] reftab;
}
int main()
{
//테스트 케이스 입력
int t;
cin >> t;
//범위 관련 예외 처리
if(t < 0) t = 1;
else if(t > 10) t = 10;
results = new bool [t];
fill(results, results+t, false);
while(t--) input();
output();
delete [] results;
return 0;
}
실제 전공과 관련된 내용은 안 올리려 했는데 이 문제의 해결방안을 도저히 모를 때,
검색한 자료 전부 위의 찾아내지 못하는 결점을 그대로 반영했더군요;
혹시라도 고민하시는 분이 계실까 싶어 잊기 쉬운 점에 대해 지적하고, 코드를 포스팅합니다.
문제의 해결 방안에 대해서는 포스트에 언급하지 않고 코드를 보면 이해할 수 있는데,
되도록 그 점은 각자 구현해보시는 게 좋겠네요. 문제 인식만 된다면 얼마든;;
