DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

데이터 전송하기

문제로 돌아가기

해설

길이 7의 해밍 부호를 사용한다. 위치 번호는 왼쪽부터 1,2,…,71,2,\ldots,71,2,…,7로 센다. 원본의 네 비트를 3,5,6,73,5,6,73,5,6,7번 위치에 차례대로 넣는다.

이 네 위치 중 비트가 1인 위치 번호를 모두 XOR한 값을 xxx라 하자. x=(b2b1b0)2x=(b_2b_1b_0)_2x=(b2​b1​b0​)로 나타내고, 1,2,41,2,41,2,4번 위치에 각각 b0,b1,b2b_0,b_1,b_2b0​,b1​,b2​를 넣는다. 그러면 완성된 문자열에서 비트가 1인 모든 위치 번호의 XOR은 x⊕x=0x\oplus x=0x⊕x=0이다.

전송 중 kkk번 비트가 뒤집혔다고 하자. 수신 문자열에서 비트가 1인 위치 번호를 XOR하면 kkk가 한 번 추가되거나 빠지므로 결과는 정확히 kkk이다. 루날리티는 그 비트를 다시 뒤집은 뒤 3,5,6,73,5,6,73,5,6,7번 비트를 읽으면 된다. 정확히 한 비트가 뒤집히므로 이 전략의 수신 문자열에서 XOR 결과는 항상 1 이상 7 이하이다.

전송 길이는 항상 7이므로 제한을 만족한다. 위치 1,2,4의 검사 비트가 뒤집히는 경우와 위치 3,5,6,7의 데이터 비트가 뒤집히는 경우 모두 같은 방식으로 복구된다.

나이브 복원 방법으로는 16가지 원본을 모두 인코딩하고, 수신 문자열과 정확히 한 위치만 다른 코드워드를 찾을 수도 있다. 서로 다른 코드워드의 거리는 적어도 3이다. 거리가 1이면 두 코드워드의 XOR 검사값이 같을 수 없고, 거리가 2이면 서로 다른 두 위치 번호의 XOR이 0이어야 하므로 모순이다. 따라서 정확히 한 비트 차이인 후보는 유일하다. 입력 크기가 고정이므로 나이브 풀이도 전체 조건을 통과한다.

주 풀이의 시간과 추가 공간은 O(1)O(1)O(1)이다. 나이브 복원은 최대 16⋅7=11216\cdot7=11216⋅7=112번의 비트 비교를 하며 역시 O(1)O(1)O(1)이다. 위치 XOR 값은 최대 7, 원본의 수치 표현은 최대 15, 길이 8의 비트마스크는 최대 255이므로 모든 정수 계산은 부호 있는 64비트 범위 안에 있다.

Solution written by GPT6

2
​