[C++] SWEA 1288: 새로운 불면증 치료법

🔗 문제

SW Expert Academy

SW Expert Academy

 

🖍 풀이

 

이 문제를 비트를 응용해보자!

다른 사람들은 풀이를 찾아보다가 이해를 못하겠어서 이해할 겸 쓰는 글이다.

비트 플래그를 쓰는 풀이를 보니 생소한 구문이 있어서 정리해보았다.

 

#include <iostream>

int main()
{
	int T; std::cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		int N; std::cin >> N;
		int k = 0, checksum = 0, tmp = N;

		while (checksum != (1 << 10) - 1)
		{
			tmp = (++k)*N;
			while (tmp) 
			{
				checksum |= 1 << (tmp % 10);
				tmp /= 10;
			}

		}
		std::cout << '#' << tc << ' ' << k*N << '\\n';

	}
}

 

---

 

먼저 비트 마스크는 집합을 표현할 수 있다. 비트를 사용하기 때문에 메모리를 적게 사용하며 빠르게 접근할 수 있는 특성이 있다.

 

1 << num

while (checksum != (1 << 10) - 1)

 

1 << num의 비트 플래그는 num번째 위치에만 비트 1이 있고, 나머지 위치에는 비트 0이 있다. 

 

 

1 << 0 == 0 00000 00001
1 << 1 == 0 00000 00010
1 << 2 == 0 00000 00100
1 << 3 == 0 00000 01000
.
.
1 << 10 == 1 00000 00000

이렇게 각 1의 위치로 어떤 숫자를 가지고 있는지 알 수 있다. 오른쪽에서 0번째에 1이 있다면 비트는 0을 뜻한다. 

 

 

 

a |= b

checksum |= 1 << (tmp % 10)

일단 이 문제 풀이에서 사용되는 tmp%10은 각 자리수를 뜻한다.

tmp가 1234일 때, tmp%10은 각 1, 2, 3 ,4가 된다. 

 

 

a|=b는 a와 b를 집합시키는 연산이다.

a = 00000 00001 // {a}
b = 00000 10000 // {b}
a|b = 00000 10001 // {a, b}

 

이런 특성을 활용한 checksum은 각 자리수의 집합체로 사용한다. 

 

 

 

while의 조건 
(1 << 10) - 1
이해하기 🤔

 

(1 << 10)은 1024이네 ?? 1빼면 1023이겠네?

🙅

 

 

 

(1 << 10)는 비트 플래그이며 1 00000 00000이다.

🙆

 

 

 

비트 빼기의 특성으로 저기서 1를 빼면??

11111 11111이다. 

 

 

10개의 1이 생겼다. 0부터 9까지 숫자가 모두 집합됐다는 뜻이다.

그렇기에 while의 종료 조건으로 사용된 것이다.

 

 

 

💾  소스

비트 마스크 없이 푼 버전

#include <iostream>

bool isAllChecked(bool visited[10])
{
    for(int i=0; i<10; ++i)
    {
        if(visited[i] == false)
            return false;
    }
    return true;
}

int main()
{
    int T; std::cin >> T;
    for(int tc =1 ; tc<=T; ++tc)
    {
        int N; std::cin >> N;
        int k = 0, tmp;
        bool visited[10] = {false, };
        
        while(!isAllChecked(visited))
        {
            tmp = (++k) * N;
            while(tmp)
            {
                visited[tmp%10] = true;
                tmp/=10;
            }
        }
        
        std::cout << '#' << tc <<' ' << k*N << '\n';
    }
	return 0;
}