6064 카잉 달력
https://www.acmicpc.net/problem/6064
◆ 문제 풀이
M N X Y가 주어질때, M N 으로 만들어지는 규칙성 배열에서 X Y가 있는지, 있다면 몇 번째인지 찾아내는 문제이다.
이해를 위해 예시를 들어보면, M,N이 각각 3,4일때
<1:1>
<2:2>
<3:3>
<1:4>
<2:1>
<3:2>
<1:3>
<2:4>
<3:1>
<1:2>
<2:3>
<3:4>
와 같은 배열이 나온다. 이 배열의 특징은, 앞자리와 뒷자리가 각각 M까지, N까지 반복된다는 것이다.
여기서 아래와 같은 특징을 찾을 수 있다..
■ 이 배열의 마지막 숫자 M N은, 최소공배수 번째의 배열이다. = M N으로 조합되는 배열의 총 개수는 M N의 최소공배수이다.
왜냐 하면, 앞자리와 뒷자리가 각각 M개, N개씩 반복되므로, 정확히 M N이 같은 자리에 오려면
두 개수가 같은 위치에 맞춰지는, 다시말해 최소공배수만큼 반복한 경우가 되어야 하기 때문이다.
■ M N중 M<N이라고 할 때, M이 1에서M까지 반복되는 동안, N은 M-N만큼 뒤로 밀린다.
<1:1><2:2><3:3><1:4> 에서 볼 수 있듯이. 앞자리(M)이 한번 돌아오고 나면, 뒷자리(N)은 M-N만큼 더 간 후에야 1로 돌아간다.
■ 모든 배열을 검색하지 않고도 앞자릿수만으로도 x y가 해당 배열에 존재하는지 알 수 있다.
예를 들어, x=2인 경우 위 규칙을 통해 <2:2> 에서 <2:3> 까지 앞자리가 2인 배열을 모두 찾을 수 있고,
앞자리가 다른 배열은 검색하지 않으므로, 알고리즘의 효율성이 증대된다.
■ 정확히 몇 번째인지도 역으로 알아낼 수 있다.
예를 들어, 앞자리가 2인 배열. <2:2> 로부터 다음 배열인 <2:1>은 3번째 배열이다.
왜냐 하면, 앞자리가 1에서 3까지 반복되고있기 때문이다. 2에서 다음 2까지 돌아오기까지 2 3 1 2 로 3만큼 증가를 거친다.
따라서, <2:4>는 세번째 "앞자리가 2인 배열" 이므로 <2:2>로부터 6번째 배열이라는것을 유추할 수 있다.
이런식으로, <2:2>로부터 얼마나 떨어져있는지를 구한 후, 첫 배열인 <2:2>가 <1:1>로부터 얼마나 떨어져있는지를 구한 다음
둘을 합하면, 결과적으로 현재 위치. 즉, 몇 번째에 해당하는지를 알아낼 수 있다.
■ 편의상 앞자리, 뒷자리로 표현했으나 사실 이 배열에서 순서는 중요하지 않다.
중요한 것은, 어느 자리가 기준이 되느냐이다. 본 알고리즘은 기준점을 작은 수로 잡아 M < N 을 전제로 하고 있지만,
실제 M > N인 값이 입력되어도, 그 순서를 바꾸고, x와 y를 서로 맞바꾸는 것으로 같은 결과를 얻을 수 있다.
◆ 코드
int main() {
int A, B, x, y, i;
int tmp, cmp;
int result;
int num;cin >> num;
int *list = new int[num];for (int k = 0; k < num; k++) { // 전체 입력 루프
cin >> A >> B >> x >> y;
int all_num;
if (A > B) { // 앞 숫자가 클 경우 비교를 쉽게 하기위해 순서를 바꾼다.
tmp = A; A = B; B = tmp;
tmp = x; x = y; y = tmp;
}for (int j = 1; j <= A; j++) {
if (A%j == 0 && B%j == 0) tmp = j; // 최소공배수를 찾기 위해 최대공약수를 구함.
}
all_num = (A / tmp)*(B / tmp)*tmp; // 최소공배수 = 배열의 총 개수cmp = x; // 시작은 x:x로 시작한다.
for (i = 1; i <= (all_num / A); i++) { // 배열 앞자리가 1~A까지를 한번 반복할때, 한번씩만 찾으면 된다.
// x인 것에서 찾으니, y만 검색하면 된다.
result = ((i - 1)*A) + x; // 만약 성공했을 경우, 이 값이 최종 result가 된다.
// 같은 수를 찾았을 때, 몇번 반복했는지를 이용하여 그 배열이 정확히 몇 번째인지 알아낸다.
if (cmp == y) break; // 만약 y가 해당 수중에 있다면 탈출. 여기서 x:x가 걸러짐.
cmp = cmp - (B - A); // 그렇지 않다면, 큰수-작은수 만큼 작아짐.
if (cmp <= 0) cmp = B + cmp; //빼고보니 0보다 작으면? 다시 최대수에서 시작한다.
if (i == (all_num / A)) { // 끝까지 왔는데 못찾았네? 그럼 -1.
result = -1;
break;
}
}
list[k] = result; // 결과값 저장
}for (int k = 0; k < num; k++) { // 출력부
cout << list[k]<<"\n";
}
return 0;
}
by. 구 본철