[BOJ 25166] 백준 25166번 - 배고픈 아리의 샌드위치 구매하기

		제4회 가톨릭대학교 프로그래밍 경진대회 (CCPC) 풀이
A		[BOJ 25165] 영리한 아리의 포탈 타기
B		[BOJ 25166] 배고픈 아리의 샌드위치 구매하기
C		[BOJ 25167] 이상한 아리의 채점
F		[BOJ 25170] 명랑한 아리의 외출
H		[BOJ 25172] 꼼꼼한 쿠기의 졸업여행
I		[BOJ 25174] 힘겨운 쿠기의 식당 개업기

1. 문제

$25166$. 배고픈 아리의 샌드위치 구매하기 (제4회 가톨릭대학교 프로그래밍 경진대회 (CCPC) B번)

백준 25166번 - 배고픈 아리의 샌드위치 구매하기 (https://www.acmicpc.net/problem/25166)

2. 풀이

동전의 종류가 $2$의 승수이고 각 동전은 1개씩 있으므로, 이를 bit를 사용해서 표현할 수 있다. 예를 들어 아리는 이진수(bitfield)로 표현했을 때 $111111111$원을 가지고 있는 셈이다.

샌드위치의 가격 $S$원이 아리가 가진 돈의 총합 $1023$원보다 적거나 같은 경우는 “No thanks”를 출력한다. 그렇지 않은 경우, 남은 돈 계산을 위해 $S$에서 $1023$을 빼고 이를 $S’$이라 지칭한다.

쿠기 또한 $2$의 승수 동전들을 각각 1개 이하로 가지고 있으므로, 가진 동전의 총 금액 $M$을 bit를 사용해서 표현 가능하다.

아리가 쿠기에게 돈을 빌릴 수 있으려면, $S’$에서 필요한 동전을 $M$이 가지고 있어야 한다. 각각의 동전은 종류별로 최대 $1$개이므로, 각각의 bit가 서로 다른 bit에 영향을 주지 않는다. 따라서, $S’$의 bit는 $1$인데 동일한 자리의 $M$의 bit가 $0$이라면, 아리는 해당 금액 1 << bit 원의 동전을 쿠기에게 빌릴 수 없다.

$S’$의 존재하는 모든 1 bit에 대해 이를 확인하여, 모두 만족하면 “Thanks”, 하나라도 만족하지 않으면 “Impossible”을 출력한다.

이때, 동전은 512($1«9$)원까지 있지만, $S-1023$의 최댓값은 $1025$ 즉, $1«10$을 포함하기 때문에, bit를 $9$가 아닌 $10$까지 확인해주어야 한다.

3. 채점 결과

4. 회고

$S-1023$의 최댓값의 크기를 간과하여 bit를 $9$까지만 검사하여 WA를 받았다.

5. 코드