[Programmers] 예상 대진표

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

프로그래머스

 

---

 

문제 해결 과정

착안

아래와 같은 규칙을 반복적으로 적용하여 대진 라운드를 계산할 수 있다. $N$ 명의 참가자에 대하여, 번호 순으로 $N / 2$ 명씩 그룹을 지었을 때,

 

• A와 B가 서로 다른 그룹에 있는 경우: A와 B가 각각 반드시 승리해서 다음 라운드로 진출해야하므로, A의 번호 및 B의 번호에 1을 더한 뒤 2로 나눈 값으로 갱신하고, 라운드 수를 증가시킨다.
• A와 B가 서로 같은 그룹에 있는 경우: 그룹 내에서 대진을 살펴봐야하므로, 참가자를 $N / 2$ 명으로 줄여 생각할 수 있고 이때 A 또는 B의 번호가 $N / 2$보다 큰 경우는 각각 $N / 2$ 만큼 빼서 번호만 갱신한다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

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

	while (n > 2)
	{
		if (a + 1 == b && a % 2 ||
			b + 1 == a && b % 2)
			break;

		n /= 2;

		if (a <= n && b > n ||
			a > n && b <= n)
		{
			answer++;
			a = (a + 1) / 2;
			b = (b + 1) / 2;
		}
		else if (a > n)
		{
			a -= n;
			b -= n;
		}
	}

	return answer;
}

 

실행 결과