💡문제
김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀 수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속한다.
마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.
💡입력
첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.
💡출력
첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.
📕문제 해석
- 두 사람이 만나게 되는 지점은 인접한 번호여야하고 번호를 2개씩 끊을때 같은 구간이어야한다.
- 같은 구간이라는 뜻은 (1,2) (3,4), (5,6) 이런 경우이다.
- 이 경우는 서로의 번호에서 1을 더하고 2를 나누어서 같은 값이 나올때이다.
- 1와2의 경우 (1+1)/2 == (2+1)/2 따라서 만나는 지점이다.
- 2와3의 경우 (2+1)/2 !=(3+1)/2 따라서 만나는 지점이 아니다.
- n을 1이 될떄까지 반복문을 돌려주고 n을 계속 2로 나눈다.
- 홀수이면은 마지막 번호가 자동으로 올라가기 때문에 무조건 짝수로 만들어줘야 하기때문에 n=n/2 +1
- 짝수인 경우 n=n/2가 될것이다.
- 만약 각각 두사람의 번호가 1번과 6번일때를 예를 들어보면
- 1번은 이기면 1번이다. 즉 홀수는 2로 나눈 몫에 1을 더한 번호가 그 다음 번호가 될것이다.
- 6번은 이기면 3번이다. 짝수는 2로 나눈 몫이 그 다음 번호가 될것이다.
- 두 사람의 번호를 조정하고 라운드를 한칸 씩 증가해준다.
- 만약 flag가 false라는 뜻은 만나지 못했다는 뜻이므로 -1을 출력하고 flag가 true라면 진행한 라운드의 숫자를 출력해주면 된다.
💡코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, a, b;
int main()
{
int cc = 1;
cin >> n >> a >> b;
bool flag = false;
while (n != 1)
{
if ((a + 1) / 2 == (b + 1) / 2)
{
flag = true;
break;
}
if (n % 2 == 0)
n = n / 2;
else
n = n / 2 + 1;
if (a % 2 == 0)
{
a = a / 2;
}
else
a = a / 2 + 1;
if (b % 2 == 0)
{
b = b / 2;
}
else
b = b / 2 + 1;
cc++;
}
if (flag == true)
{
cout << cc;
}
else
cout << -1;
}
✔느낀 점
단순한 수학적 계산 문제다. 두 사람이 만나는 지점을 잘 생각해주면 쉽게 풀 수 있다.
