비트마스킹 연습하기1(백준 25166,12833)

1. 문제

 

25166번: 배고픈 아리의 샌드위치 구매하기 (acmicpc.net)

25166번: 배고픈 아리의 샌드위치 구매하기

 

1,2,4,8,16,32,64,128,256,512원짜리 동전만 사용가능할때, 이들을 하나씩 가지고 있는데, 친구에게 돈을 빌려서라도 샌드위치 가격만큼 내줄 수 있는지 아닌지 알아보는 문제

 

2. 풀이

 

브론즈1인데.. 어렵다..

 

비트마스킹 이론 공부 했는데 뭔가 응용하기가 어렵다고 해야하나..?

 

연습좀 많이 해봐야겠지

 

이 문제의 핵심은 일단 "1,2,4,8,16,32,64,128,256,512원짜리 동전만 사용가능"이라는 것이다

 

아리나 쿠기가 동전을 각각 1개씩만 가지고 있기 때문에 예를 들어 샌드위치 가격이 1원인데,

 

아리가 2원 가지고 있다면 2원짜리 동전 1개만 가지고 있다는 것으로

 

이러면 샌드위치를 살 수가 없다.. 거스름돈을 내줄수가 없어서

 

그래서 단순히 샌드위치 가격 - 아리 돈 <=0 라고만 해서는 문제를 풀수가 없다

 

----------------------------------------------------

 

1,2,4,8,16,32,64,128,256,512원짜리 동전을 각각 1개씩 가지고 있으므로 비트마스킹을 이용해서

 

최초 아리가 가진 돈의 집합을 비트가 0~9번까지 켜진 비트열로 표현할 수 있다

 

from sys import stdin

s,m = map(int,stdin.readline().split())

ahri = (1<<10)-1

 

다음에 샌드위치의 가격 s에 대하여..

 

s도 비트마스킹으로 비트열로 표현할 수 있겠지

 

아리가 가진 돈으로 샌드위치 가격을 지불한다는 것은 무슨뜻일까?

 

샌드위치 가격을 비트열로 표현하고

 

아리가 가진 돈을 비트열로 표현해서.. 이 비트로

 

샌드위치 가격의 비트를 제거하면 되겠지

 

즉, 집합 s에서 집합 아리가 가진 비트를 빼주면 되겠지

 

그러므로 s와 아리의 차집합을 구해줘야한다

 

만약 샌드위치 가격이 1023원 이하이면.. 

 

 

 

참고로 샌드위치 가격이 1023원 이하이면, 아리는 반드시 샌드위치를 자기 돈으로 구매 가능하다

 

이게 무슨뜻이냐면 1,2,4,8,16,32,64,128,256,512 1개씩만 사용해서 1023이하의 모든 자연수를 반드시 만들 수 있다

 

 

 

 

샌드위치 가격이 1024원 이상이면.. 모든 돈을 써도.. 줘야할 돈이 남아있다

 

 

그랬을때, 만약 공집합이라면? 아리가 가진 돈만으로 샌드위치를 살 수 있다는 뜻

 

from sys import stdin

s,m = map(int,stdin.readline().split())

ahri = (1<<10)-1

if s & ~(ahri) == 0:
    
    print('No thanks')

 

근데 공집합이 아니라면, 줘야할 돈이 남아있다는 뜻인데

 

남은 돈은 어떻게 구하냐?

 

이거는 비트마스킹이 아니야 그냥 s-ahri로 구해야 남은 돈을 구하는거지

 

그러면 이제 쿠기의 돈 m원을 빌려

 

위와 똑같은 원리로 s-ahri와 m을 비트마스킹으로 표현하고

 

s-ahri와 m의 비트를 비교해야겠지

 

둘의 차집합은? s-ahri에만 존재하고, m에는 존재하지 않는 비트들의 집합

 

s-ahri의 비트들에서 m의 비트들을 제거한 집합

 

둘의 차집합이 공집합이라면? m의 비트들을 모두, 혹은 일부를 사용하면 s-ahri의 모든 비트를 제거할 수 있다

 

=> 쿠기의 돈을 빌려서라도 샌드위치를 살 수 있다

 

차집합이 공집합이 아니라면? m의 비트들을 모두 사용해서 제거하더라도 s-ahri의 비트가 남아있다

 

=> 쿠기의 돈을 빌려도 샌드위치를 살 수가 없다

 

from sys import stdin

s,m = map(int,stdin.readline().split())

ahri = (1<<10)-1

if s & ~(ahri) == 0:
    
    print('No thanks')

else:
    
    remain = s - ahri
    
    if remain & ~(m) == 0:
        
        print('Thanks')
    
    else:
        
        print('Impossible')

 

 

3. 문제2

 

12833번: XORXORXOR (acmicpc.net)

12833번: XORXORXOR

 

수 a에 대하여 b와 xor연산을 c회 했을때 결과를 출력하는 문제

 

4. 풀이

 

생각없이 이렇게 했더니 시간초과가 났다

 

from sys import stdin

a,b,c = map(int,stdin.readline().split())

for _ in range(c):
    
    a = a ^ b

print(a)

 

 

알고보니 c가 1000000000까지 가능한데 시간은 0.2초 안에 해야하더라

 

그래서 생각해보니까 XOR연산이 어떤 특징을 가지고 있는데

 

XOR연산은 원래 비트를 뒤바꾸는 성질이 있어

 

toggle 시키는데 사용한다고 배웠었어

 

서로 같은 비트면 0이 되고 서로 다른 비트면 1이 되잖아

 

근데 b는 고정된 수니까...

 

고정된 수와 xor연산을 계속 한다면?

 

예를 들어 b = 1일때, 1 ^ 1 = 0

 

다시 0 ^ 1 = 1

 

다시 1 ^ 1 = 0

 

다시 0 ^ 1 = 1

...

 

b=0이면.. 1 ^ 0 = 1

 

1 ^ 0 = 1..

 

혹은 0 ^ 0 = 1

 

1 ^ 0 = 0

 

0 ^ 0 = 1

 

1 ^ 0 = 0

 

....

 

따라서 xor연산을 짝수번 하면 자기 자신이 되고 홀수번하면 xor연산을 한번만 한것과 같다.

 

from sys import stdin

a,b,c = map(int,stdin.readline().split())

if c % 2 == 1:
    
    a = a ^ b

print(a)

 

5. 되돌아보기

 

기본적인 비트연산을 사용하긴 했는데 그래도 어렵네 

 

왜 비트마스킹은 응용이 유난히 안되는것 같냐

 

정수랑 집합이랑 비트열을 왔다갔다해야하니 까다롭다;;

 

답은 연습밖에 없다