(C++) - 프로그래머스(2017 팁스타운) : 예상 대진표

https://programmers.co.kr/learn/courses/30/lessons/12985?language=cpp# 

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

수학 문제였습니다.

 

풀이방법

 토너먼트 방식이므로 n을 2로 나누어가며 a와 b가 왼편과 오른편에 위치해 있으면 해당 라운드에는 만난다는 것을 알 수 있습니다. 재귀를 이용해 해결합니다.

 

* a와 b는 누가 더 큰지 명시되어 있지 않기 때문에 여러 입력에 대해 고려해야합니다.

* 만약 a와 b가 모두 n/2기준으로 오른편이라면 왼편으로 옮겨주기 위해 다음 재귀 호출 시 인자로 a와 b를 각각 /2한 것을 반영해 넘겨줍니다.

Code

#include <bits/stdc++.h>
using namespace std;

int dfs(int n,int a, int b, int exponents){
    if(!n) return 1;
    if(min(a,b) <= n / 2 && max(a,b) > n/2) return exponents;
    if(min(a,b) > n / 2 && max(a,b) > n / 2) return dfs(n/2, a - n/2, b - n/2, exponents - 1);    
    else return dfs(n/2, a, b, exponents - 1);    
}

//2로 나눠가면서 서로 다른 그룹이라면 return 
int solution(int n, int a, int b){
    int exponents = 0;
    while(1 << exponents != n) exponents++;
    return dfs(n, a, b, exponents);    
}

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

8 7 4 

답

3

 

input

8 8 1

답

3

 

input

8 5 6

답

1

 

input

8 5 8 

답

2

 

input

16 1 5 

답

3

 

input

16 11 16 

답 3