[프로그래머스] 예상 대진표 C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/12985#qna

프로그래머스

 

전체 코드

#include <iostream>
using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    
    if(a>b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    
    while(1)
    {
        if((a/2)+(a%2)==(b/2)+(b%2))
            break;
        a=(a/2)+(a%2);
        b=(b/2)+(b%2);
        answer++;
    }
    
    answer++;
    return answer;
}

 

풀이 방법

먼저 1 2 3 4번 참가자가 있다고 하자

1 2번 참가자가 붙어 이긴 승자는 1번을 부여받고,

3 4번 참가자가 붙어 이긴 승자는 2번을 부여받는다.

 

마찬가지로 풀이의 핵심은

원이 아닌 도넛처럼 생긴 것이 A번 참가자와 B번 참가자(경쟁자)라고 하자.

이 둘이 매칭이 되었다고 하면 다음번의 번호는 동일하게 부여받을 것이라는 것이다.

위의 그램을 보자 A(2번) B(4번)이라고 하자.

 

결국 매칭 되어 붙는다면 다음번에 같은 번호를 부여받게 될 것이다.

 

다음번의 번호는 현재 번호가 x라고 하면

x/2 + x%2로 구해진다.

 

풀이 코드를 해석하겠다.

if(a>b)
{
	int temp=a;
    a=b;
    b=temp;
}

문제의 조건에서 a<b라는 말이 없으니 항상 b가 더 크게 조정을 해준다.

이것이 없다면 테스트 케이스에서 문제가 발생해 시간 초과가 난다.

 

while(1)
{
    if((a/2)+(a%2)==(b/2)+(b%2))
    	break;
    a=(a/2)+(a%2);
    b=(b/2)+(b%2);
    answer++;
}

if문은 다음번 매칭 번호가 동일하게 된다면 붙게 될 예정이므로 break 해준 것이다.

그게 아니라면 A, B 각각 매칭을 이겼다고 가정하고 다음번 번호를 부여해준다.

 

answer++;

붙게 될 예정까지 while문을 돌게 구현했으니 이제 붙어야 하니 answer++을 해주었다.

 

 

틀린 코드를 보이겠다.

while(a+1!=b)
{
	...
}

while문을 이렇게 짰는데

바로 붙어있다면 다음번에 매칭이 될 줄 알았는데 예외가 있었다.

 

아래의 반례이다.

 

A는 4번 B는 5번인데 붙어있음에도 불구하고 다음번에 매칭이 안된다.