<프로그래머스 C++> 예상 대진표 풀이 ( ceil() )

문제

토너먼트 대회에서 N명이 참가하고, 매 라운드마다 인접한 번호끼리 대결한다. 그리고 이기는 사람이 다음 라운드에 올라간다.

A번 참가자와 B번 참가자가 몇 번째 라운드에서 만나는지 return하는 문제이다.

단, 두 참가자는 만나기 전까지 항상 이긴다고 가정한다.

---

풀이 아이디어

매 라운드마다 참가자 번호가 절반으로 줄어든다. 

A와 B의 번호를 매 라운드마다 갱신하면서 두 번호가 갈라지는 순간이 만나는 라운드이다.

 

다음 라운드에서의 번호는 ceil(번호 / 2.0)으로 갱신한다.

1번↔2번 → 이긴 사람은 다음 라운드 1번  →  ceil(1/2.0)=1, ceil(2/2.0)=1
3번↔4번 → 이긴 사람은 다음 라운드 2번  →  ceil(3/2.0)=2, ceil(4/2.0)=2

 

A = 4, B = 7을 예시로 들어보면

1라운드: a=ceil(4/2.0)=2,  b=ceil(7/2.0)=4  →  2 ≠ 4
2라운드: a=ceil(2/2.0)=1,  b=ceil(4/2.0)=2  →  1 ≠ 2
3라운드: a=ceil(1/2.0)=1,  b=ceil(2/2.0)=1  →  1 == 1 (true) → 3라운드에서 만남

---

문제 풀이

#include <iostream>
#include <cmath>
using namespace std;

int solution(int n, int a, int b)
{
    int round = 0;
    while(1)
    {
        round++;
        a = ceil(a / 2.0);
        b = ceil(b / 2.0);
        if(a == b) break;
    }
    return round;
}

---

Ceil()을 쓰는 이유

Ceil()은 <cmath> 헤더에 정의된 함수로 올림 연산을 수행한다.

올림 연산 말고도 다음과 같은 함수들이 있다.

함수	설명	예시
ceil(x)	올림	ceil(3.5) = 4
floor(x)	내림	floor(3.5) = 3
round(x)	반올림	round(3.5) = 4

 

이 중에서 Ceil() 함수를 쓴 이유는 토너먼트에서 홀수 번호는 승리해서 다음 라운드로 넘어가게 되면 올림된 번호를 받게 된다.

7번 → ceil(7/2.0) = ceil(3.5) = 4번

 

이를 2.0으로 나누는 이유는 int / int 나눗셈은 정수 나눗셈이 되어 소수점이 버려지기 때문이다.

7 / 2   = 3   (정수 나눗셈 — 내림)
7 / 2.0 = 3.5 (실수 나눗셈 — ceil 적용 가능)

소수점이 버려지게 되면 올림 연산이 불가능해져 2.0으로 나누는 것이다.

---

코드 흐름

1. 라운드 반복

while(1)
{
    round++;
    a = ceil(a / 2.0);
    b = ceil(b / 2.0);
    if(a == b) break;
}

매 라운드마다 a와 b를 다음 라운드 번호로 갱신한다.

두 번호가 같아지면 그 라운드에서 만나는 것이다. 따라서 번호가 같아질 때 break로 반복문을 빠져나간다.

 

2. 두 사람이 만나는 조건

if(a == b) break;

위 설명과 같이 같은 번호가 되었다는 것은 같은 조에 배정되었다는 의미이기 때문에 이 시점의 round를 return하면 그게 정답이 된다.

---

트러블슈팅

a와 b의 갱신 방식을 잘못 선택함

처음엔 a와 b를 이런식으로 갱신했다.

float A;
A = ceil(a / 2.0);  
a /= 2;          //정수 나눗셈으로

 

ceil로 계산한 값과 정수 나눗셈으로 갱신한 값이 달라서 일부는 맞고 일부는 틀린 결과가 나왔다.

그래서 매개변수를 ceil로 갱신하는 방법으로 통일해서 이 오류를 수정했다.

// 수정한 부분
a = ceil(a / 2.0);
b = ceil(b / 2.0);

---

핵심포인트

 

• 다음 라운드 번호는 ceil(번호 / 2.0)으로 구한다.
• int / int는 정수 나눗셈이므로 반드시 2.0으로 나눠야 한다.
• a == b가 되는 순간이 매칭되는 라운드이므로 그 때의 round를 리턴한다.