[C++][프로그래머스][Lv2] 12985.예상 대진표

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

프로그래머스

 

---

❗풀이방법

:  N이 범위가 넓어서 for문은 사용하면 안 되겠다고 생각했다.

 

: 대진표를 그려보면 이렇게 된다. 
1번과 2번은 두번째에 1이 되고, 

3번과 4번은 두번째에 2가 되고,

5번과 6번은 두번째에 3이 되고............

N-1과 N번은 두번째에 ( N-1 + 1 ) / 2 번째가 된다.

: 같은 '그룹'에 속해있는지 검사방법

-> 위의 사진에서 마지막에는 [1,2] 번이 대결하게 된다.

-> 한번더 순서를 정했을 때, 둘 다 1번이 된다. -> 같은 그룹에 속해있다. 

 

❗틀린 시도 

int aOrder = a;
int bOrder = b;

while (true) 
{
	if (abs(aOrder - bOrder))
	{
		break;
	}

	// a가 짝수/훌수이면?
	if (aOrder % 2 == 0)
		aOrder /= 2;
	else
		aOrder = aOrder / 2 + 1;

	// a가 짝수/훌수이면?
	if (bOrder % 2 == 0)
		bOrder /= 2;
	else
		bOrder = bOrder / 2 + 1;

	//cout << aOrder << " / " << bOrder << endl;
	answer++;
}

: while문을 break하는 조건문에서,

A순서와 B순서의 차이가 1이면 만난다,라고 생각했는데

만약 A가 2번, B가 3번 일 때는 같은 그룹이 아닌데도 조건에 만족하기 때문에 테스트케이스에서 틀렸었다.

[1,2][3,4]로 그룹이 이루어져 있는데, A-B가 1은 맞지만 같은 그룹이 아니다.

 

---

int solution(int n, int a, int b)
{
    int answer = 0;

    int aOrder = a;
    int bOrder = b;

    while (true) 

    {
        // 예외 : 처음에 2, 3이면 오류남, [1,2][2,3] 그룹이 이렇게 되어야함
        // 만약 둘이 붙어있는 그룹이면 [1,2] -> 한번 더 순서를 정했을 때 같은 순서가 된다.
        if (aOrder == bOrder)
        {
            break;
        }

        // 3,4일 때 (3+1)/2 = 2, (4+1)/2=3
        aOrder = (aOrder + 1) / 2;
        bOrder = (bOrder + 1) / 2;

        answer++;
    
    }

    return answer;
}

: [3,4]가 대전을 했을 때, 번호가 홀수일 때 짝수일 때로 조건을 나눴었다.

그런데 먼저 +1을 더하고 2로 나누게 되면 홀수와 짝수 둘 다 올바른 순서를 구할 수 있다.

 

---

https://github.com/kimYouChae

kimYouChae - Overview