백준 25166: 배고픈 아리의 샌드위치 구매하기[java]

이번에는 난이도가 브론즈 1로 조금 상승했네요.

하지만  비트마스킹 알고리즘을 통해 쉽게 풀 수 있을 것으로 보입니다.

 

두리 나라의 돈이 1, 2, 4, 8, 16 ... 512원이 존재합니다. 아리가 각각 1개씩 가지고 있으니 총 1023원이 됩니다.

1023을 2진수로 나타내면 1111111111 입니다. (10자리)

즉, 모든 화폐를 한번 사용 |  사용 안해서 1023 이하 숫자를 만들 수 있다는 의미가 됩니다.

힌트

---

• 1023 아래의 숫자는 빌릴 필요가 없습니다. 이 경우는 No thanks 출력
• 비트 연산자로 표현하였을 때 "빌려야 할 돈" 과 "쿠기와 가진 돈"이 같아야 합니다.
  [즉, (빌려야할 돈 & 쿠기가 가진돈 ) == 빌려야할돈 이라면 도움을 받아 살 수 있습니다.]

 

코드

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args)throws Exception{
		new Main().sol();
	}

	private void sol() throws Exception{
		StringTokenizer st = new StringTokenizer(br.readLine());
		int S = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		if(S < 1024) System.out.println("No thanks");
		else{
			int namoji = S - 1023;
			if((namoji & M) == namoji) System.out.println("Thanks");
			else System.out.println("Impossible");
		}
	}
	
}

조금만 생각하면 쉽게 풀리는 문제였습니다.

봐주셔서 감사합니다

 

- fin -