[BOJ] 5370 Which Way (C++)

5370번: Which Way

난이도: B2
시간 제한: 1초
메모리 제한: 128 MB

---

문제

You are trapped in Jabba’s Palace. You have a coded map that describes the way out from your current location. The map contains a sequence of positive integers. Each integer corresponds to one of three directions (left, straight, right). To determine the direction you must convert the number into binary (base two with no leading 0s). If the binary number has more 0’s than 1’s go left. If the binary number has the same number of 0’s and 1’s go straight, and if it has more 1’s than 0’s go right. Your job is to read the sequence of positive integers and print the directions to find your way out. 

Here are three example of converting positive (decimal) integers into binary and then into a direction.

Decimal	Binary	Direction
17	10001	left
9	1001	straight
22	10110	right

---

입력

A sequence of positive integers, one per line

---

출력

The correct directions (left, straight, right) for escaping the Jabba’s Palace. You should write each move (left, straight, right) on a separate line with no extra lines.

---

풀이

문제 자체는 양수 n을 2진수로 표현하였을 때, 0과 1의 개수를 세서 0이 더 많으면 "left", 같으면 "straight", 1이 더 많으면 "right"를 출력하는 매우 쉬운 사칙연산 문제이다.

 

다만 초심자에겐 약간의 어려움이 있을 수 있다.

왜냐하면 테스트 케이스의 개수를 안알려주는 문제이기 때문이다.

보통 한글문제들 중엔 이러한 입력이 없는데 외국어 문제를 풀다보면 심심찮게 만나볼 수 있는 유형이다.

 

이를 처리하는 방법은 조만간 글로 정리해서 올리겠다만, 이미 알고 있다면 문제는 알될테고 그냥 눈치껏 아~ 이렇게 쓰는 거구나 하고 넘어가도 좋다.

 

본론으로 돌아오자.

 

10진수 숫자를 2진수로 만드는 방법은 2로 나누어 떨어진 값(0 or 1)들을 역순대로 나열하는 것이다.

그런데 이 문제는 2진수로 바꾸었을 때,  0과 1의 순서는 궁금하지 않고, 오로지 개수에만 집중한다.

따라서 굳이 2진수 배열을 만들어 다시 for으로 셀 필요 없이 나눠 떨어진 값을 카운팅 하면 된다.

 

#include <iostream>
#include <array>
#include <string>

#define FastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

using namespace std;

int main()
{
    FastIO;

    while (true)
    {
        int n;
        cin >> n;

        if (cin.eof())
            break;

        array<int, 2> cnt = { 0,0 };
        do
        {
            cnt[n % 2]++;
            n /= 2;
        } while (n > 0);

        string result = (cnt[0] == cnt[1] ? "straight" : (cnt[0] > cnt[1] ? "left" : "right"));
        cout << result << '\n';
    }
}

 

이런 류의 문제를 자주 풀어본 사람이라면 이상한 점을 느낄 수 있다.

문제 조건에서 n은 양수라고 했기 때문에, 굳이 do-while문으로 작성하지 않고,

while문 만으로 이런 식으로 작성할 수 있기 때문이다.

while (n > 0)
{
    cnt[n % 2]++;
    n /= 2;
}

 

하지만 이 문제엔 빅풉이 하나 있다.

실제론 입력에 0이 들어가는 입력 테스트 케이스에 오류가 있는 문제라는 것.

그리고 0은 2진수로 0이기 때문에 cnt = { 1,0 }이어서 "straight"가 아닌 "left"를 출력해야한다.

 

그렇기 때문에 입력에 0이 들어오더라도 무조건 한 번은 while문을 돌게끔 do-while문을 사용해 주었다.

만약 추후에 이 문제의 테스트 케이스가 수정된다면 do-while문이 아닌 while문만을 사용해도 문제 없을 것이다.