[C++로 풀이] 예상 대진표 (DFS) ⭐⭐

📌 예상 대진표

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

using namespace std;

void DFS(int& a, int& b, int& count, int start, int end, int n)
{
    if (n == 1){
        count++;
        return;
    }
    
    int middle = (start + end) / 2;
    if (a >= start && a <= middle && b >= start && b <= middle){
        count++;
        DFS(a, b, count, start, middle, n / 2);
    }
    else if (a >= middle + 1 && a <= end && b >= middle + 1 && b <= end){
        count++;
        DFS(a, b, count, middle + 1, end, n / 2);
    }
    else
        return;
}

int solution(int n, int a, int b)
{
    int answer = 0;
    int count = 0;
    
    DFS(a, b, count, 1, n, n);
    
    int exp = 0;
    while(n > 1){
        n /= 2;
        exp++;
    }
    answer = exp - count;

    return answer;
}

• 내가 생각했던 규칙
  • 범위를 절반씩 나눴을 때
    • 그 절반으로 나눈 같은 범위 안에 a와 b가 둘 다 들어 있어 있다면 👉 카운팅한다.
    • a와 b가 같은 범위 안에 있지 않고 각각 다른 범위 안에 속해 있다면 👉 더 이상 카운팅 하지 않고 break
  • 최종적인 카운르를 트리의 높이(n이 16이라면 4가 된다. 즉 제곱근..!)에서 빼주면 정답.

그래서 약간 이분 탐색과 비슷하게 절반으로 나눠서 왼쪽 범위 안에 둘 다 있다면 카운팅하고 또 절반으로 나누는 것을 진행해야 하기 때문에 왼쪽 범위를 전체 범위로 한 DFS를 호출 시켰다. 반대로 오른쪽 범위 안에 둘 다 있따면 카운팅하고 오른쪽 범위를 전체 범위로 한 DFS를 호출했다. 둘이 같은 범위 안에 속해있지 않다면 그건 DFS 종료 조건이 된다.

• 예를 들어 n이 16 이고 a가 12, b가 15라면!
  • [1,2,3,4,5,6,7,8] [9,10,11,12,13,14,15,16]
    • a와 b는 둘 다 오른쪽 범위 안에 속한다. count = 1 오른쪽 범위로 DFS
  • [9,10,11,12] [13,14,15,16]
    • adhk b는 각각 다른 범위 안에 속하므로 break
• 최종적인 답은 16의 제곱근인 4에서 1을 뺀 3이 된다.

🚀 다른 풀이

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    
    while(a != b){
        a = a / 2 + a % 2;
        b = b / 2 + b % 2;
        answer++;
    }

    return answer;
}

이 문제를 DFS 로 푼 사람은 나 밖에 없을 것 같다.. 이렇게 간단한 풀이가 있는데 ㅠ ㅠ.. 현타..

• 짝수번 참가자의 경우 👉 다음 라운드로 가면 n = n / 2 번이 된다.
• 홀수번 참가자의 경우 👉 다음 라운드로 가면 n = n / 2 + 1 번이 된다.

짝수의 경우 n % 2가 0이기 때문에 위는 n = n / 2 + n % 2 로 일반화 할 수 있다. 번호가 같아질 때까지 answer를 카운팅하면 그게 답이 된다. 번호가 같아진다는 것은 만났다는 것을 의미함.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기