[SWEA/D3] 10726 이진수 표현

🔗 문제

SW Expert Academy

SW Expert Academy

 

✏️ 풀이

문제에서 대놓고 비트마스크라고 힌트를 주어서 어렵지 않은 문제지만 생각해보지 못한 풀이 방법을 배워서 풀이를 남긴다.

 

일단 문제를 읽자. (위 사이트 참고)

 

M이 최대 10^8승 (1억)이므로 배열로 순회하면 C++ 기준 1000ms 이내에 제출해야 하는데 바로 시간초과행이다 🙂

그에 비해 N은 최대 30이므로 절대 시간초과가 안 걸릴 줄 알았는데 시간초과에 걸렸다.

테스트케이스가 1만개 중에 9883개를 맞추길래 부랴부랴 FAST IO를 적용해서 맞출 수 있었다.

 

FAST IO를 습관화 하자.

1000ms를 못 넘겨서 시간초과 났던 것이 13ms로 통과되었다.

#include<iostream>

using namespace std;

bool getAnswer(const int N, const int M)
{
    if(M%2 == 0) // M이 짝수
        return false;
    
    for(int i=0; i<N; ++i)
    {
        if((M & (1 << i)) == 0)
            return false;
    }
    return true;
}

int main(int argc, char** argv)
{
    //FAST IO 없으면 시간 초과
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    int test_case;
    int T, N, M;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N >> M;
        std::cout << "#" << test_case << " " << (getAnswer(N, M) ? "ON" : "OFF") << "\\n";
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

 

댓글에서 배운 점

완전 천재 댓글을 보았다.

이게 무슨 말인지 모르겠다면 차근 차근 따라와보세요!

 

 

[N개의 비트가 모두 1인 비트 만드는 방법]

 

여기서 규칙을 만들 수 있다. 1의 개수가 N개인 비트는 (2^N - 1)에 해당한다.

예를 들어, N=3일 때는 2^3 - 1 = 7이 됩니다. 이진수로는 111이다!

mask = (2^N - 1) // N개의 1로 이루어진 bitmask

 

 

이 mask를 잘 이용하면 아래처럼 생각할 수 있다. 

M&mask과 mask값이 같다면 마지막 N개의 비트가 1인 ON이 된다. 

 

 

 

또 다른 방법으로는 M % (1 << N) 을 하는 방법도 있다. 10진수 연산이 끝난 후 이걸 2진수로 만들면 딱 N자리의 수만 남는다.  

 

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T, N, M;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N >> M;
        
        // 방법 1
        int mask = (1 << N) - 1;
        printf("#%d %s\n", test_case,  ((M & mask) == mask) ? "ON" : "OFF");
        
        // 방법 2
        printf("#%d %s\n", test_case,  (M % (1 << N) == (1 << N) - 1) ? "ON" : "OFF");
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

이것도 FAST_IO 적용하면 더 빠를 수도 있겠다..

누가 해보면 댓글 좀 ~~ ㅎㅎ