백준 문제풀이 - 1057 번

링크 -> https://www.acmicpc.net/problem/1057

1. 요약 및 풀이방법

• 총 N명의 참가자 중, 서로 이웃해있는 참가자끼리 경기를 해 토너먼트 방식으로 올라갈 때,
  첫 배정 번호 a번 김지민과 b번 임한수가 몇번째 라운드에서 만날지 구하는 문제이다.

• 토너먼트 경기는 둘중 한명이 승자로 올라가기 때문에,
  한 라운드가 끝나면 경기 인원이 절반으로 줄고,
  각 참가자 번호도(이전 라운드의 순서를 유지하기 때문에,) 절반으로 감소한다.
  이때 홀수인 경우를 잘 고려하여 각 수를 감소시킨다.

• 김지민과 임한수의 번호가 1차이 나면서 앞선 사람의 번호가 홀수일때,
  두 사람은 해당 라운드에서 맞붙게된다.

따라서 위의 조건을 재귀함수 종료조건으로 하여 재귀함수를 이용했다.

2. Code

#include <iostream>
#include <algorithm>

# define PARTICIPANT 0
# define NUM_A 1
# define NUM_B 2

int g_list[3], g_answer = 1;

void input()
{
    std::cin >> g_list[PARTICIPANT] >> g_list[NUM_A] >> g_list[NUM_B];
    if (g_list[NUM_A] > g_list[NUM_B])
        std::swap(g_list[NUM_A], g_list[NUM_B]);
}

void  divide()
{
    for (int i = 0; i < 3; i++)
    {
        if (g_list[i] % 2 == 0)
            g_list[i] /= 2;
        else
            g_list[i] = (g_list[i] / 2) + 1;
    }
}

void solution()	// 재귀함수.
{
    if (g_list[NUM_B] - g_list[NUM_A] == 1 && g_list[NUM_A] % 2 == 1)
        return ;	// 재귀함수 종료.
    divide();
    g_answer++;
    solution();
}

void print()
{
    std::cout << g_answer << std::endl;
}

int main()
{
    input();
    solution();
    print();
    return (0);
}

3. 학습 내용

• 큰 수가 먼저 들어오는 경우 algorithm 라이브러리에 있는 swap함수를 이용하였다.

• 문제에서 말한 "만약 서로 대결하지 않을 때는 -1을 출력한다." 의 경우는
  "일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다." 의 가정으로
  발생하지 않는 경우이다.
  실제에서는 고민할만한 경우 중 하나이지만 위의 문제에서는 고려할 사항이 아니다.
  이렇게 제외하는 경우 또한 잘 확인하여 불필요한 코드를 줄이자.

4. 결과