압축은 본디 '식별자'를 만드는 과정입니다. 동일한 파일은 압축 결과가 같으며, 다른 파일은 압축 결과가 달라야 합니다.
즉, 여기서 압축 알고리즘은 N개의 파일을 정의역으로 하고, B비트 이하의 이진 문자열을 공역으로 하는 일대일 함수입니다.
이 문제는 주어진 N과 B에 대해 이러한 일대일 함수가 있는지 묻는 문제입니다.
두 번째 예시인 (1, 0)을 예로 들면, 첫 번째 파일은 길이 0의 이진 문자열로 표현할 수 있습니다. 약간 말이 안 된다고 생각할 수 있겠지만, 정보 엔트로피 관점에서 볼 때 파일이 1개라는 건 불확실성이 없는 상태이기 때문에 엔트로피가 0입니다. 때문에 yes입니다.
물론, (2, 0)은 no입니다. B = 0이면 '아무 것도 없는 상태' 1개밖에 없어서 2개의 상태를 표현할 수 없기 때문입니다.
대신 B = 1이면 "", "0", "1" 총 3개의 이진 문자열이 생깁니다. 이러면 N <= 3까지는 yes, N >= 4부터는 no입니다.
이런 성질을 이용하면, B의 값에 따라 yes가 되는 N의 범위를 수학적으로 표현할 수 있습니다. 이를 통해 yes와 no를 출력하시면 됩니다.
skesswswkk 9달 전
문제가 이해가 되지 않인 질문 올립니다
문제 설명 짧게라도 부탁드립니다