8개의 댓글이 있습니다.
-
-
일루 -
안녕하세요 이번에도 문제 에디토리얼을 안쓰고 방치플레이하는 중인 일루입니다.. -0-
음.. 제 입장으로는 단순 recursive가 편한데요, 아마 코드를 그런 방식으로 고치시면 코드 길이가 훨씬 줄어들 겁니다. 다만 써주신 방식으로 하면 non-recursive하게도 짤 수가 있고, 변수 건네주기 등등의 overhead가 없으므로 실행속도를 훨씬 빠르게 할 수 있다는 장점이 있습니다. (MM같은데서 최적화한다면 이렇게 짤 듯 하네요)
그리고 이 문제는 (6*2)^6개의 경우를 체크해서 푼 사람들도 많지만 (6^6)*6만 보고 푼 사람들도 꽤 있더군요. 6^6에서 어떤 음을 연주할지를 결정하고, 그 다음에 어떤 string을 기준으로 하여(즉 다른 string들은 이 string에서 짚는 위치보다 안쪽으로는 짚지 않도록) 짚을지를 결정하여 계산합니다. 이렇게 하면 효율이 꽤 많이 상승합니다.
아 물론 저는 (생각이 없어서)그냥 다 돌렸습니다. 리플을 빙자한 에디토리얼이 되었군용... 네개나 밀렸는데.. -0-
16년 전 link
-
-
-
Megalusion -
Gumx 경기과고학생 아닌데요ㅜㅜ
16년 전 link
-
-
-
Megalusion -
아니요 ㅋㅋ 저 아이디가 저에요
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
nocut98
먼저 이번 SRM은 (전 참가를 못했지만) 한국분들의 선전이 두드러졌습니다.
먼저 ainu7 본좌님이 top 10안에 드셨고- (ㄷㄷㄷ;;;)
2부리그에서는 첫 출전한 gumx란 분이 1등을 먹고, (아마 경기과학"고등학생"인 것으로 보이는) unbing이란 분도 나란히 14위...(ㄷㄷㄷ;;;) 또 yoonhaerim 이란 아뒤 가진 (아마도 여성 탑코더로 생각됩니다!!) 분도 첫 출전하여 2문제를 푸셨더군요.
아무튼 문제 해석 들어갑니다.
문제
일단 12도 음계가 있고(A, B, C, C#, ...) 기타를 치는데, 각 줄마다 기본 음계가 있고, 여기서 손을 짚으면 음이 올라갑니다. 짚는 곳의 차이가 벌어질수록 짚기 어려워지므로 요구되는 소리를 모두 내면서도 최소 차이로 짚기를 원합니다.
주의할 점은 요구되는 chord를 벗어나는 소리가 있으면 안됩니다.
chord중에 빼먹는 게 있으면 당연히 안됩니다. 음계는 회전하는 성질이 있으므로 A~G보다는 G~A가 더 가깝습니다.
strings은 최대 6개고 chord는 그 이하입니다. 한 string에서 2개의 소리가 날 순 없습니다.
해설
strings(각 줄, n개), chord(요구되는 소리, m개) 가 있다면 각 줄마다 chord를 하나씩 매칭 시켜서 모든 경우를 수를 세도 될 만합니다. m^n(6^6)이면 되죠. 하지만, 이러면 답이 안 나오기도 합니다. 바로 음계의 회전하는 성질을 고려하지 않아서 그렇습니다. G를 짚었으면 같은 음계의 A보다는 다음 음계의 A가 더 가까운 거죠. 다다음 음계까지는 계산하지 않아도 됩니다. 그래서 12^6이 됩니다
빨리 푼 사람들은 6^6으로 계산해서 모든 chord가 들어가지 않은 경우를 빼버리고 2^6연산을 합니다(12^6은 600ms정도 걸리는데, 중간에 한번 제거해주도록 했더니 15ms 안으로 다 풀리더군요)
질문
이 문제를 알고리즘으로 푸는 방법은 감이 잘 안옵니다. 그래프로 어찌어찌 풀 수 있을지 고민하다가 좌절하고 푼 사람들 소스 보니 그냥 경우의 수를 다 체크하는 방식이더군요 ㅡ.ㅜ;;
이 문제는 제 추측으로는 양 사이드에 있는 점들을 연결해서 최소의 거리를 가지도록 하는 문제랑 비슷하다고 봅니다. 매칭되어 버리면 다른 애들이 기회를 잃어 버리거든요. 비슷한 문제를 알고스팟에서 봤던 거 같은데 어떤 문제인지 모르겠네요 ㅡ.ㅜ
아이디어
사실 제가 굳이 문제의 해설을 올리려는 이유는 동적 for문에 대해서 얘기해 볼려고 하는 건데요. its_(n_,0); \
its_[pos_] = 0;\ code; strings, vector chord) { str, chd; flags(m,false);
이번 문제는 recursive하게 푼 사람들이 대다수 입니다. 근데 저 같은 경우는 옛날에도 질문을 했었지만, 문제에서 m^n을 체크하면 되는 건데 recursive 함수를 만들려고 하면 변수들을 넘겨줘야 하기 때문에 좀 머리가 아플라고 합니다.
그래서
dynamic_for(its, m,n) {
// m^n 경우의 모든 수가 벡터 its안에 들어옵니다. 길이는 n인 벡터고 값은 0~(m-1) 이 들어오는 거죠
}
이러면, 변수로 무엇을 넘겨줘야 할지 고민하지 않고, 그냥 해당 값과 매칭해서 풀면 됩니다. 이번 같은 경우는 m에 해당하는 0~(m-1)의 값에 각각의 음이 매칭되겠죠 그리고 함수가 없으니 전역 변수 같은 거 없어도 되고, 코드의 가독성도 높아집니다.
이번 문제를 대상으로 제가 짜본 코드는 아래와 같습니다.
[code c++]
// continue와 break의 차이가 없음
#define DF_START(m__,n__, its_) int m_(m__),n_(n__); \
vector
while(*its_.rbegin() != m_) { \
for(int k_=0;k_<1;++k_)
#define DF_END(its_) int pos_(0); \
while(pos_
++pos_;\
}\
if(pos_ == n_) break;\
}
class GuitarChords {
public:
map
int stretch(vector
int n = sz(strings);
int m = sz(chord);
int rr(INT_MAX);
code["A"] = 0; code["A#"] = 1; code["B"] = 2; code["C"] = 3; code["C#"] = 4; code["D"] = 5;
code["D#"] = 6; code["E"] = 7; code["F"] = 8; code["F#"] = 9; code["G"] = 10; code["G#"] = 11;
vector
FSZ(i,0,strings) { str.push_back(code[strings[i]]); }
FSZ(i,0,chord) { chd.push_back(code[chord[i]]); }
// m^n 공간을 탐색하고 값은 its라는 벡터로 나옴
DF_START(m, n, its) {
vector
F(i,0,n) { flags[its[i]] = true; }
// 일단 모든 음을 연주 안하면 넘어가버림
if(find(all(flags), false)!=flags.end()) continue;
// 2^n 의 경우의 수를 체크하고, 값은 its2라는 벡터로 나옴
DF_START(2,n,its2) {
int minv(INT_MAX), maxv(0);
F(i,0,n) {
// 여기서 이것들 간의 거리를 구한다(min, max)
int dist = (chd[its[i]]+12*its2[i]) - str[i];
if(dist != 0) {
minv = min(minv, dist);
maxv = max(maxv, dist);
}
}
// save
int val(0);
if(minv<=maxv) val = maxv - minv + 1;
rr = min(rr, val);
} DF_END(its2);
} DF_END(its);
return rr;
}
[/code]
근데 이런 생각을 제가 했을리는 만무하고, 아마 일반적인 해법이 있을 꺼 같은데요. 다른 분들은 어떻게 처리하시는지 궁금합니다. 다들 recursive하게 푸는 것이 자연스러워져서 이런 고민 안하실려나 ㅡ.ㅡㄱ;;
추가로 아직 매크로가 일반성을 갖기에 부족합니다. break;같은 건 안 먹고, 중간에 좀 더 디테일한 동작들이 고려되지 않았죠.
하고 싶은 말은 그니까 문제에 따라서 동적for 문을 이용하면 쉽게 풀 수 있는 문제가 있다. 이거죠.
아무튼 이번에도 문제 에디토리얼을 빙자한 질문인 듯 ㅡ.ㅡ;;;
16년 전