[BOJ]1057 토너먼트(S4, C++)

📋 개요 

이어서 포스팅할 글은 난이도가 실4이다. 문제를 읽고 어떻게 풀지 아이디어가 떠오르지 않아서 결국 2시간을 다 소진하고 말았는데 답을 보니깐 크게 고민해야될 문제는 아니였다.....

 

앞으로 더 노력해야겠다ㅠㅠ

 

2024.02.27 - [Algorithm/Problem] - [BOJ]1380 귀걸이(S5, C++)

[BOJ]1380 귀걸(S5, C++)

 

---

🧩 문제

https://www.acmicpc.net/problem/1057

1057번: 토너먼트

📝  형식 

📥 입력	📤 출력
첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.	첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	16 1 2	1
2	16 8 9	4
3	1000 20 31	4
4	65536 1000 35000	16
5	60000 101 891	10

 

🥲  정답코드

---

📖  해설 및 느낀점

# 풀이

다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

 

문제에서 이 지문이 나를 엄청나게 헷갈리게했다. 처음에는 pair 키워드를 사용해서 원래 기존의 값을 남기고 라운드가 진행될때 마다 새로운 값을 갱신해줘야겠다고 생각했다.(사실 이게 맞는 풀이 일지도 모르겠다)

그 후에 김지민과, 임한수가 만난다면 break를 걸어 만나기전 횟수를 카운트 하는 코드를 작성했다.

 

물론 작성을 했지만 디버깅에 어려움이 있었고, 아무리봐도 내 풀이가 아닌거 같은 생각이 들었고, 답을 찾아봤는데 해당 답은 아래와 같다.

 

문제에 나와있듯이 1번과 2번이 대결해서 승리한 사람은 1번이된다. 마찬가지로 3번과 4번의 대결에서 승리한 사람은 당연히 2번이 된다.

 

위의 방식대로 식을 세우면 (n+1)/2가 다음 라운드의 진출되는 번호이다.

 

여기서 우리가 알 수 있는 점은 1번과 2번중 아무나 이겨도 상관없이 다음 라운드에서는 무조건 1번이 된다는 것이다. 3번과 4번도 마찬가지로 아무나 이겨도 상관 없이 무조건 2번이 된다는 점에 주목을 해야한다.

 

그렇다면, 우리가 찾아야하는 임함수와 김지민의 대결 라운드를 어떻게 찾을 수 있을까?

"둘의 숫자가 같으면 둘의 대결이 성사된다."

 

1번에 김지민, 2번에 임한수가 있다고 가정하자. 

위의 방식대로 대입을 하면, 

(1+1)/2 = 1

(2+1)/2 = 1

 

둘다 1이 나오게 되는데 이는 둘의 대결이 성사되었다고 볼 수 있다. 

이런식으로 while문을 통해서 둘의 식의 값이 같을 때까지 round수를 증가하면서 돌리면 답이 나온다.

 

#느낀점

실버 문제부터는 뭔가 아이디어적인 요구를 많이하는 느낌이 많이 든다. 지문도 살짝 길어지고.... 난이도는 사실 알고보면 어렵지 않지만, 뭔가 그냥 구현으로 생각하고 풀면 뭔가 찝찝하다는 생각이 많이든다.