문제
N개의 서로 다른 메시지를 b비트로 인코딩할 수 있는지 판별하라.
입력
메시지 수 N과 비트 수 b가 주어진다.
출력
인코딩 가능하면 yes, 불가능하면 no를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 | yes |
풀이
가변 길이 코딩으로 표현 가능한 최대 메시지 수와 비교한다.
- b비트 이하의 코드로 표현 가능한 메시지 수는
2^(b+1) - 1이다 - N이 이 값 이하이면
yes, 초과이면no를 출력한다
핵심 아이디어: 1비트부터 b비트까지 모든 길이의 코드를 사용하면 2^1 + 2^2 + ... + 2^b = 2^(b+1) - 2개 + 빈 코드 1개 = 2^(b+1) - 1개의 메시지를 구분할 수 있다.
코드
N, b = map(int, input().split())
print("yes" if N <= 2 ** (b + 1) - 1 else "no")복잡도
- 시간: O(1)
- 공간: O(1)