Codeforces Round #739 (Div. 3) Problem. B

https://codeforces.com/contest/1560/problem/B
Codeforces Round #739 (Div. 3)

B. Who’s Opposite?

TimeLimit	MemoryLimit	Difficulty	Tags
1 S	256 MB	800	math

Attr	SubNo	SolveTime	Time	Memory	Accept?
1	126327661	+40min	1000 ms	3700KB	Time limit
2	126332184	+8min (48m)	77 ms	3600KB	Wrong answer
3	126336434	+8min (56m)	93 ms	3700KB	Accepted

---

문제 요약

원형의 식탁에서 회의를 하는데 인원은 모르고(짝수이다) 모든 사람은 서로 마주보는 상대가 있다.
각자의 번호는 1부터 시작해서 시계방향으로 숫자를 매긴다.

a 와 b가 마주보고 있을 때, c와 마주보고 있는 사람의 번호를 구하여라.

피드백

Input

1-st line : Testcase (1 <= t <= 10⁴)
각 Testcase 마다
t-th line : space로 구분된 3개의 정수 (1 <= a, b, c <= 10⁸)

Output

각 Testcase 마다
1개의 정수 d : c와 마주보고있는 숫자
답이 여러개일시 아무거나 출력, 답이 없으면 -1출력

---

문제 풀이

이문제 또한 어려운 문제는 아니였다. 규칙만 잘 찾으면 되는 문제였지만, 예상외로 해맸었다.

Attr 1 (Time Limit exceeded on test 2)

첫시도부터 굉장히 복잡하게 생각을 했는데 일단 무조건 규칙이 있을것이라고 예상을 하였다. 그래서 열심히 규칙을 찾아본 결과..
서로 마주보는 a와 b를 기준으로 a-n은 b-n을 마주보고 있다는 사실을 알게 되었다.
또한 계속 빼가다가 어느 한 수가 0에 도달하게 되면,
큰수 + (큰수 - n - 작은수)가 원탁에 앉아있는 총 인원 수가 나왔다. 복잡하다
또는 큰수-n과 작은수의 값이 같아지면, 큰수 + (작은수 - n) 의 값이 총 인원수가 되었다.

결국 for문으로 돌려서 위 두 케이스중 하나의 케이스가 나오게 되면 Loop를 빠져나가고 남은 값들을 계산하여 값을 도출해 냈다. 물론 결과는

시간 초과
최대 시간복잡도가 10⁴X10⁸ = 10¹²(약 1조…)가 나와버린다…

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int big = max(a, b);
        int small = min(a, b);
        int i, meet = small - 1;
        int result = -1;
        for (i = big-1; i > small && meet > 0; i--, meet--) {
            if (result == -1) {
                if(i == c) result = meet;
                else if(meet == c) result = i;
            }
        }
        //cout << "i = " << i << ", m = " << meet << endl;
        if(result == -1 && i > small && meet == 0) {
            if(c > small && c <= i) result = big + (c-small);
            else if(c > big && c <= (big + (i-small))) result = small + (c-big);
        }
        cout << result << endl;
    }
    
    return 0;
}

Attr 2 (Wrong answer on test 2)

시간초과로 한대 맞고난 뒤 for문으로 해결할 수 없는 문제라는 사실을 문제를 본지 40분만에 알아차렸다. 결국 다른 규칙을 찾다가 한가지 핵심적인 규칙을 깨닳을 수 있었다.

서로 마주보고있는 두 수의 간격은 무조건 전체 인원수의 절반이 된다.
이 규칙을 찾은 후 이 규칙을 가지고 코드를 짰다. 기본적으로 두 수의 간격을 구하고, 그 간격을 기준으로 c값이 작으면 전체 인원수의 절반을 더해주고, c값이 크면 전체 인원수의 절반을 빼주는 형식으로 정답을 구했다. 또한 몇가지의 예외사항을 넣어두었다.

앞에서 했던 for문 뻘짓을 왜했는지 이해가 되지 않았지만 8분만에 코드를 짜고 제출을 하였다.
그러나 결과는

오답
공식에는 문제가 없었다. 다른 예외사항이 있는듯했다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int a, b, c, result = -1;
        cin >> a >> b >> c;
        int big = max(a, b);
        int small = min(a, b);
        int dis = big - small;
        if(c > dis) result = c-dis;
        else if (c <= dis) result = c + dis;
        if(result > dis*2 || big > dis*2) result = -1;
        cout << result << endl;
    }
    
    return 0;
}

Attr 3 (Accepted!)

결국 또하나의 예외를 찾아내고 나서야 문제를 해결할 수 있었다.

“c가 전체 인원수보다 크면: a와 b가 마주보고 있는 원탁에는 c는 존재할 수 없다.”
결론적으로 이 예외조건을 추가하니 정상적으로 코드가 Accept 되었다.

---

최종 해설

서로 마주보고있는 두 수의 간격은 무조건 전체 인원수의 절반이 된다.

a와 b를 사용하여 전체 인원수의 절반을 구하고, 그 수를 기준으로 하여 c에 따라서 결과값을 구해주면 된다.
규칙만 잘찾으면 어렵지않게 풀 수 있는 문제였다. 괜히 반복문으로 접근해서 시간만 날렸다

?c가 전체 인원수의 절반보다 작거나 같으면:
정답 : c + 전체 인원수의 절반;

?아니면 c가 전체 인원수의 절반보다 크면:
정답 : c - 전체 인원수의 절반;

만약: 정답이 전체 인원수보다 크면:
정답 : -1;
제대로된 원탁이 아니다.

또는: c가 전체 인원수보다 크면:
정답 : -1;
a와 b가 마주보고 있는 원탁에는 c는 존재할 수 없다.

또는: a와 b중에 큰 수가 전체 인원수보다 크면:
정답 : -1;
a와 b중에 큰 수는 제대로된 원탁에 존재할 수 없다.

---

최종 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int a, b, c, result = -1;
        cin >> a >> b >> c;
        int big = max(a, b);
        int small = min(a, b);
        //총 인원수의 절반
        int dis = big - small;
        if(c > dis) result = c-dis;
        else if (c <= dis) result = c + dis;
        //답이 나오지 않는 경우 
        if(result > dis*2 || big > dis*2 || c > dis*2) result = -1;
        cout << result << endl;
    }
    
    return 0;
}

느낀점

원형탁자 -> 숫자 -> 순서대로 -> 반복문!! 일것이라고 안일하개 생각한게 문제가 되었다.
결국 초반에 반복문으로 계속 고민을 하다가 시간만 날려버리게 되었다.
문제를 해결하는 방법에 편견을 가지지 말고 다양한 방법을 생각해 봐야할 것 같다.