실제 대회에서는 열어보기만 할 정도로 시간이 없었지만(99점 받은 250점 짜리 문제의 삽질로 인해 ㅠ_ㅠ), 끝나고 풀어본 후 기록 남기는 차원에서 남깁니다
문제의 내용은 간단합니다.
그냥 여러 색깔 공이 각각의 상자에 들어있는데, 1상자에는 한가지의 색깔만 남기려고 하고, 같은 색깔이 중복되지는 않도록 하려고 합니다. 하나의 공을 이동할 때 1이라면, 최소 이동 횟수는 몇이 될지를 물어보는 문제입니다(600점 짜리 문제에서 조커의 존재만 빠져 있는 상황이죠. 점수 계산 방법도 달라져서 풀이방식도 완전히 달라지구요)
해답도 간단합니다.
그냥 각 색깔별로 하나씩 남겼을 때 최대의 값을 구해서 (예를 들어 빨간공만 남기기로 한 상자는 빨간공들은 안 움직여도 되니까요) 전체의합 - 최대값 해주면 됩니다. 주의할 점은 각 색의 최대값을 구하면 하나의 박스에 겹치는 색이 나올 수도 있어서 모든 경우의 수를 다 체크해 봐야 합니다. 그냥 모든 경우의 수를 체크하면 TLE가 나고, DP를 이용해서 결과를 저장해가면서 풀면 됩니다.
DP를 사용하지 않고 recursive하게 돌리면, 50^14정도가 나오고
DP를 사용하면, 50*14*2^14 정도가 나옵니다. 시스템테스트로 체크해보면 최대 84ms 정도 나오더군요.
코드도 간단한 편입니다. 음 저는 그냥 for문 돌리는 방법이 먼저 생각나던데, 대다수의 사람들은 recursive하게 풀었더군요. 그게 좀 더 안정적이어서 그런 걸까요? 가급적 상위랭커들의 소스를 참조해보려 했으나 제 눈에는 암호로 밖에 안 보여서 ㅠ_ㅠ
[code c++]
#define two(N) (1<<(N))
#define contain(S,N) (((S)&two(N))!=0)
class MarblesRegroupingHard {
public:
int minMoves(vector boxes) {
int n = sz(boxes);
vector > bx(n);
int sum(0);
// 배열에 값을 저장합니다.
FSZ(i,0,boxes) {
istringstream iss(boxes[i]);
for(int x; iss >> x; bx[i].push_back(x));
sum += accumulate(all(bx[i]), 0);
}
int m = sz(bx[0]);
// DP로 저장공간에 저장해 가면서 최대값을 구합니다.
vector > memo(2, vector(two(m), 0));
for(int j=0; j<m; ++j) {
memo[1][1<<j] = bx[0][j];
}
for(int i=1; i<n; ++i) {
for(int set=0; set<two(m); ++set) { memo[0][set] = memo[1][set]; }
for(int j=0; j<m; ++j) {
for(int set=0; set<two(m); ++set) {
if(!contain(set, j)) {
int t = set + (1<<j);
memo[1][t] = max(memo[1][t], memo[0][set] + bx[i][j]);
}
}
}
}
// 결과값을 반환합니다 (모든 구슬의 수 - 안 움직여도 되는 구슬의 최대값)
return sum - *max_element(all(memo[1]));
}
[/code]
제가 궁금한 것은 (사실은 질문만 하기 미안해서 같이 올린 글이라능 ㅎㅎㅎ)
결국 이 문제의 핵심은 2차원 배열에서 한 x,y축에 1개의 값만 선택할 때 최대값을 이루는 배열을 어떻게 구할 수 있느냐 하는 것인데 최대치의 합을 구할 때, 가능한 방법이 위처럼 일일히 해보는 방법밖에 없는 것인지 궁금합니다.
저는 위에 한글로 번역해주신 문제를 읽자마자 "헝가리안 메소드"를 사용하면 되겠구나! 라는 생각을 했습니다.
팀노트북에 있는 소스를 긁어서 붙인다음에 살짝 수정을 가해줬더니 962점이 나오네요 [...]
일반적으로 헝가리안 메소드는 minimum을 구하지만, 약간의 trick을 사용하면 maximum을 구하는것도 가능하니까요.
제가 원하던 답이네요- 2부리그의 Hard는 보통 약간 복잡한 라이브러리 정도면 바로 풀수 있는 규정화된 문제가 나오는 듯 합니다. 1부리그 문제는 풀어본 적이 없지만 아마 mid, hard의 라이브러리들을 기본으로 깔고 응용하는 문제들이 나오겠죠?
헝가리안으로 푼 사람은 거의 없는 듯 합니다.- 저도 만들어서 저장해 놔야 겠네요 ㅋ
nocut98
실제 대회에서는 열어보기만 할 정도로 시간이 없었지만(99점 받은 250점 짜리 문제의 삽질로 인해 ㅠ_ㅠ), 끝나고 풀어본 후 기록 남기는 차원에서 남깁니다 boxes) { > bx(n); > memo(2, vector(two(m), 0));
문제의 내용은 간단합니다.
그냥 여러 색깔 공이 각각의 상자에 들어있는데, 1상자에는 한가지의 색깔만 남기려고 하고, 같은 색깔이 중복되지는 않도록 하려고 합니다. 하나의 공을 이동할 때 1이라면, 최소 이동 횟수는 몇이 될지를 물어보는 문제입니다(600점 짜리 문제에서 조커의 존재만 빠져 있는 상황이죠. 점수 계산 방법도 달라져서 풀이방식도 완전히 달라지구요)
해답도 간단합니다.
그냥 각 색깔별로 하나씩 남겼을 때 최대의 값을 구해서 (예를 들어 빨간공만 남기기로 한 상자는 빨간공들은 안 움직여도 되니까요) 전체의합 - 최대값 해주면 됩니다. 주의할 점은 각 색의 최대값을 구하면 하나의 박스에 겹치는 색이 나올 수도 있어서 모든 경우의 수를 다 체크해 봐야 합니다. 그냥 모든 경우의 수를 체크하면 TLE가 나고, DP를 이용해서 결과를 저장해가면서 풀면 됩니다.
DP를 사용하지 않고 recursive하게 돌리면, 50^14정도가 나오고
DP를 사용하면, 50*14*2^14 정도가 나옵니다. 시스템테스트로 체크해보면 최대 84ms 정도 나오더군요.
코드도 간단한 편입니다. 음 저는 그냥 for문 돌리는 방법이 먼저 생각나던데, 대다수의 사람들은 recursive하게 풀었더군요. 그게 좀 더 안정적이어서 그런 걸까요? 가급적 상위랭커들의 소스를 참조해보려 했으나 제 눈에는 암호로 밖에 안 보여서 ㅠ_ㅠ
[code c++]
#define two(N) (1<<(N))
#define contain(S,N) (((S)&two(N))!=0)
class MarblesRegroupingHard {
public:
int minMoves(vector
int n = sz(boxes);
vector
int sum(0);
// 배열에 값을 저장합니다.
FSZ(i,0,boxes) {
istringstream iss(boxes[i]);
for(int x; iss >> x; bx[i].push_back(x));
sum += accumulate(all(bx[i]), 0);
}
int m = sz(bx[0]);
// DP로 저장공간에 저장해 가면서 최대값을 구합니다.
vector
for(int j=0; j<m; ++j) {
memo[1][1<<j] = bx[0][j];
}
for(int i=1; i<n; ++i) {
for(int set=0; set<two(m); ++set) { memo[0][set] = memo[1][set]; }
for(int j=0; j<m; ++j) {
for(int set=0; set<two(m); ++set) {
if(!contain(set, j)) {
int t = set + (1<<j);
memo[1][t] = max(memo[1][t], memo[0][set] + bx[i][j]);
}
}
}
}
// 결과값을 반환합니다 (모든 구슬의 수 - 안 움직여도 되는 구슬의 최대값)
return sum - *max_element(all(memo[1]));
}
[/code]
제가 궁금한 것은 (사실은 질문만 하기 미안해서 같이 올린 글이라능 ㅎㅎㅎ)
결국 이 문제의 핵심은 2차원 배열에서 한 x,y축에 1개의 값만 선택할 때 최대값을 이루는 배열을 어떻게 구할 수 있느냐 하는 것인데 최대치의 합을 구할 때, 가능한 방법이 위처럼 일일히 해보는 방법밖에 없는 것인지 궁금합니다.
16년 전