2017_탑스다운_#2. 예상 대진표

코딩테스트 연습 - 예상 대진표 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 예상 대진표

예상 대진표

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

---

입출력 예NABanswer

8

4

7

3

입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

---

( 문제 해설 )

0. for문을 돌면서 두명씩 짝지어서 라운드마다 n/2씩 줄이면서 하는 방법은 복잡하고 오류가 날 가능성이 많다.

 

0 - 1. 그렇다면 어떻게 해야할까? 일단 A와 B는 무조건 이긴다고 합니다 때문에

A가 3번 이라면 3번과 4번이랑 떠서 무조건 이깁니다 그렇게 되면 => 2번이 되겠죠.. 그와중에 1번과 2번은 싸워서 둘 중 이긴놈이 1번이 될겁니다.

여기서 무언가 느낌이 오나요?

3 vs 4 중 3번이 A든지 4번이 A든지 이기는 쪽은 2번이 됩니다. 3=> 2, 4 => 2

1 vs 2 중 1번이 A든지 2번이 A든지 이기는 쪽은 1번이 됩니다. 1 => 1, 2 => 1

...THINKING~...

알겠나요?

 

3 // 2 => 1.XXX => 올림 => 2

4 // 2 => 2 => 올림 => 2

 

...이런식의 메커니즘이 되는 겁니다.

 

1. 이렇게 된다면 임의의 번호를 가진 A, B가 정해지면 각각 A, B를 위의 매커니즘 처럼 해주되 할 때마다 +1 라운드를 더해줍니다.

2. 해주고 나서 A == B라면 라운드수를 리턴해주면 되는 문제입니다.

 

---

[ 코드 ]

 

# 2. 예상 대진표
import math


def vsmatch(a, b):
    a = math.ceil(a / 2)
    b = math.ceil(b / 2)

    return a, b


def solution(n, a, b):
    answer = 0

    while True:
        if a == b:
            return answer
        
        else:
            a, b = vsmatch(a, b)
        answer += 1

 

 

 

---

 후기

 

일일이 하려고 하면 어려운 문제고,

쉽게 생각하면 쉬운 문제입니다.문제를 풀때 곧이 곧대로 푸는게 정답일때도 있지만아닐때도 많습니다.문제를 풀면서 그러한감이 왔을때 과감히 과거에 했던 코드를 잠시 미루고재작성하는 과감한 선택도문제풀이능력을 향상시키는 중요한 부분 같습니다.