[Baekjoon] 토너먼트(BOJ 1057)

👀 문제 설명

문제

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

 

출력

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

 

예제 입력 1

16 8 9

 

예제 출력 1

4

 

✍🏻풀이

매 라운드마다 인접해있는지 확인해준다! (1, 2) (3, 4) (5, 6) (7, 8) .. 이런 식으로 인접해야 대결한다.

while문을 사용했다. while문 안에서 if문을 사용해 인접해있고, 더 작은 숫자를 2로 나눈 나머지가 2일 때 break하는 방식을 택했다. (다른 블로그 찾아보니까 훨씬 쉽게 한 방법도 많은 것 같다..!)

만약 인접해있지 않다면 다음 라운드로 진행될 때 index를 현재 index / 2 한 값으로 바꿔준다.

 

서로 대결하지 않을 때는 -1을 출력하라고 했는데, 이 경우를 무시해도 정답이 나온다. (아마 언젠가는 둘이 대결하게 돼서 그런듯..?)

 

필요한 변수

int N : 몇 명이 참가하는가?

int x : 김지민(or 임한수)의 번호

int y : 임한수(or 김지민)의 번호

 

알고리즘

1. N, x, y를 입력받는다.

2. 김지민과 임한수가 대결을 하는 라운드를 구할 때까지 while문을 돌린다.

2-1. while문 안에서 둘의 번호가 인접해있고, 더 작은 수를 2로 나눈 나머지가 2인지 확인한다. (이 때 break)

2-2. 2-1에 충족하지 않다면 다음 라운드로 진행해야 함. 다음 라운드로 진행할 때마다 현재 index를 index / 2의 값으로 바꾼다.

2-3. round를 +1 해준다.

3. 김지민과 임한수가 대결하는 라운드를 구하면, round를 출력한다.

 

코드

//
//  BOJ_1057.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/06/17.
//  Copyright © 2020 조수민. All rights reserved.
//
//  토너먼트(https://www.acmicpc.net/problem/1057)

#include <stdio.h>
#include <iostream>

using namespace std;

int N, x, y;

int getRoundNum()
{
    int round = 1;
    
    while (1)
    {
        // 인접해있고, 더 작은 숫자를 2로 나눈 나머지가 1일 때 break
        if (x > y && (x == y + 1) && (y % 2 == 1))
        {
            break;
        }
        else if (y > x && (y == x + 1) && (x % 2 == 1))
        {
            break;
        }
        
        // 다음 라운드로 진행될 때마다 현재 index의 /2 값으로 바뀐다..
        if (x % 2 == 0)
            x = x / 2;
        else
            x = (x + 1) / 2;

        if (y % 2 == 0)
            y = y / 2;
        else
            y = (y + 1) / 2;
        
        // round + 1 해준다.
        round += 1;
    }
    
    return round;
}

int main()
{
    // input
    cin >> N;
    cin >> x >> y;
    
    // output
    cout << getRoundNum() << endl;
    
    return 0;
}