백준 12036번 Dance Around The Clock - C++(cpp) 풀이

---

 

1. 어떤 수 N이 짝수라면 양옆은 항상 홀수이고, 어떤 수 N이 홀수라면 양옆은 항상 짝수이다.
2. 어떤 수 N의 오른쪽 수는 항상 N의 왼쪽 수보다 2 작다.
3. K가 짝수인 경우 한 턴이 지나면 왼쪽 번호가 2 커지고, K가 홀수인 경우에는 2 작아진다.

 

1. 어떤 수 N이 짝수라면 양옆은 항상 홀수이고, 어떤 수 N이 홀수라면 양옆은 항상 짝수이다.

 짝수와 홀수를 짝지어 자리를 바꾸기 때문에 턴이 계속되어도 항상 짝수 홀수가 번갈아서 배치되는 규칙이 있다.

 

2. 어떤 수 N의 오른쪽 수는 항상 N의 왼쪽 수보다 2 작다.

 그리고 또 어떤 수의 오른쪽 수 = 왼쪽 수 - 2라는 규칙이 있다.

 

3. K가 짝수인 경우 한 턴이 지나면 왼쪽 번호가 2 커지고, K가 홀수인 경우에는 2 작아진다.

 위에서 발견한 규칙들을 적용하면 된다. K가 홀수라고 하자. K의 왼쪽은 K+1이고, N턴이 지나면 2N 만큼이 커져있을 것이므로 left = (K+1+2N) % D이다. 이때 D턴이 지나면 원상 복구되므로, N턴 후의 결과는 N% D턴 후의 결과와 같다. 따라서 left = (K+1 + (N% D)*2) % D로 바꾸어 쓸 수 있다. K가 짝수일 때는 2N 만큼이 줄어들도록 계산하면 된다.

반응형

---

#include <iostream>

using namespace std;

long long D, K, N;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    
    for (int t=1; t<=T; t++) {
        cin >> D >> K >> N;
        
        long long l, r;
        
        if (K % 2 != 0) l = (K+1 + (N%D)*2) % D;
        else l = (K+1 - (N%D)*2 + 2*D) % D;
        
        r = (l - 2 + D) % D;
        
        if (l == 0) l = D;
        if (r == 0) r = D;
        
        cout << "Case #" << t << ": " << l << " " << r << "\n";
    }

    return 0;
}