[ BOJ ] 25166 : 배고픈 아리의 샌드위치 구매하기 ( BRONZE 1 ) / C, Python

문제

"두리"라는 나라가 있다. 이 나라에서 사용되는 동전은 1원, 2원, 4원, 8원, 16원, 32원, 64원, 128원, 256원, 512원짜리 이렇게 총 10가지이다. 이 나라의 국민인 아리는 10가지의 동전을 각각 1개씩 총 10개를 가지고 있다.

아리는 샌드위치를 사러 빵집에 가기로 했다. 그런데 빵집에 잔돈이 없어서 샌드위치 가격 S 을 정확하게 지불하지 않으면 샌드위치를 살 수 없다고 한다. 아리가 가지고 있는 동전들을 가지고 계산을 하던 도중 아리의 친구인 쿠기가 마침 빵집에 들어왔다. 쿠기는 10종류의 동전 중에 모든 종류가 아니라 일부 종류의 동전을 각각 1개씩 가지고 있다. 쿠기가 가지고 있는 동전들의 총 금액은 M 원이다. 쿠기는 아리에게 자신이 가진 돈 중에 일부 또는 전체를 흔쾌히 빌려줄 수 있다고 한다. 단, 아리는 양심 상 자신의 돈을 남긴 상태로 쿠기에게 돈을 빌릴 수는 없어서 자신이 가진 돈을 모두 사용한 후에 부족한 금액에 대해서 쿠기에게 돈을 빌리려고 한다.

아리는 상황에 따라 쿠기에게 인사를 다르게 하려고 한다. 아리는 과연 쿠기에게 뭐라고 할지 구해보자!

입력

첫 번째 줄에 공백을 기준으로 샌드위치 가격 S(1 ≤ S ≤ 2048)와 쿠기가 가지고 있는 금액 M(1 ≤ M ≤ 1023)이 주어진다.

출력

아리의 돈으로만 살 수 있다면 "No thanks"를 출력하고, 쿠기의 도움을 받아야만 살 수 있다면 "Thanks" 그리고 쿠기가 돈을 빌려주더라도 샌드위치를 살 수 없다면 "Impossible"를 출력한다.

풀이 과정

아리는 1원, 2원, 4원, 8원, 16원, 32원, 64원, 128원, 256원, 512원 동전을 1개씩 가지고 있으므로 1원부터 1023원까지는 정확하게 지불할 수 있다! -> 2진수 10자리로 1부터 1023을 표현하는 원리와 같다.

 

1024원 이상부터는 쿠기의 도움을 받아야 하는데, 쿠기가 s - 1023 원을 정확히 지불할 수 있어야 살 수 있고, 그렇지 않으면 샌드위치를 살 수 없다.

 

쿠기가 가지고 있는 돈 또한 위의 동전 원리와 똑같으므로 2진수로 나타낼 수 있는데, 쿠기가 가지고 있는 돈과 s - 1023 원을 AND 연산 했을 때 s - 1023 원이 나온다면 쿠기가 정확히 도움을 줄 수 있다. 

 

쿠기가 가지고 없는 동전 (0) 을 s - 1023 원에서는 지불해야 한다 (1) 거나,

쿠기가 가지고 있는 동전 (1) 을 s - 1023 원에서는 지불할 필요가 없(0) 거나, 

쿠기가 가지고 없는 동전 (0) 을 s - 1023 원에서 지불할 필요가 없(0) 으면 AND 연산 시 0이 나오고,

 

쿠기가 가지고 있는 동전 (1) 을 s - 1023 원에서 지불해야 한다 (1) 면 AND 연산 시 1이 나오게 된다.

비트마스킹 기법을 이용해 쿠기가 가지고 있는 돈 과 s - 1023 원을 AND 연산 하면, s - 1023 원을 정확히 지불해야 하는 동전 중 쿠기가 어느 동전을 가지고 있는지를 확인할 수 있다. 만약 s - 1023 원이 AND 연산 결과로 나온다면 s - 1023 원을 지불하는 데 필요한 동전을 모두 가지고 있다는 뜻이므로 정확히 지불할 수 있다.

 

C언어에서는 비트 연산 & 보다 == 가 연산자 우선순위가 높음을 주의하자.

C

#include <stdio.h>

int main(void) {
    int s, m;
    scanf("%d %d", &s, &m);

    if (s <= 1023) printf("No thanks");
    else if (((s - 1023) & m) == (s - 1023)) printf("Thanks");
    else printf("Impossible");
    return 0;
}

Python

import sys
input = sys.stdin.readline

s, m = map(int, input().rstrip().split())
if s <= 1023: print('No thanks')
else:
    if (s - 1023) & m == (s - 1023): print('Thanks')
    else: print('Impossible')