skesswswkk   9달 전

문제가 이해가 되지 않인 질문 올립니다

문제 설명 짧게라도 부탁드립니다

evenharder   9달 전

압축은 본디 '식별자'를 만드는 과정입니다. 동일한 파일은 압축 결과가 같으며, 다른 파일은 압축 결과가 달라야 합니다.

즉, 여기서 압축 알고리즘은 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달 전

@evenharder

만약 B = 2면 "", 00, 01, 11 이렇게 4까지 yes인건가요?

evenharder   9달 전

아닙니다. 2자리 이하의 이진 문자열의 개수를 생각해보시기 바랍니다.

B = 0일 땐 {""}, B = 1일 땐 {"", "0", "1"}입니다. 당연히 B = 2일 땐 B = 1일 때의 문자열들도 포함이 됩니다.

skesswswkk   9달 전

@evenharder

그럼 B = 2일 때는 "", 0, 1, 00, 01, 11 이렇게 6까지 yes인건가요?

skesswswkk   9달 전

3일 때는 "", 0, 1, 00, 01, 11, 001, 010, 100, 101, 110, 111 이렇게 12까지 yes인건가요?

evenharder   9달 전

약간 잘못 생각하고 계신 것 같습니다. B = 2일 때 되는 문자열은 위의 6개 말고 하나 더 있습니다. B = n에서 B = n+1로 갈 때 몇 개의 이진 문자열이 추가될지 수학적으로 생각해보시기 바랍니다.

skesswswkk   9달 전

@evenharder

"10"이 빠졌네요 감사합니다

skesswswkk   9달 전

@evenharder

설명해주신대로 코드를 작성해 보았습니다.

가능한 경우의 수를 sum으로 구해준 후 b가 sum 보다 작거나 같으면 "yes"를 출력토록 하였습니다.

어느 부분에서 틀렸는지 봐주실 수 있으신가요?

evenharder   9달 전

입력 조건상 n, tmp, sum의 값이 int의 범위를 벗어날 수 있어서 그렇습니다. 이 값을 전부 long long 타입으로 바꾸는 걸 권장드립니다.

그리고 pow 함수는 double를 반환하기 때문에 실수 오차가 발생할 수 있습니다. 2^jisu 꼴을 long long으로 계산하고 싶으시다면 1LL << jisu로 할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.