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

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

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

01 격자 만들기

문제로 돌아가기

해설

N≥5N \geq 5N≥5에서는 기본적으로 각 행을 0, 1, 0, 1, …\ldots…로 채운다. 같은 문자가 이어지면 오른쪽으로, 문자가 바뀌면 위나 아래로 한 칸 이동하면 문자열을 만들 수 있다. 첫 번째 열은 값을 반대로 두어 완전히 번갈아 나오는 두 문자열을 모두 세로 경로로 처리한다.

첫 번째 열을 뒤집으면 전부 같은 문자인 문자열을 가로로 만들 수 없으므로 (2,N)(2,N)(2,N)을 0, (3,N)(3,N)(3,N)을 1로 바꾼다. 이 두 칸을 이용하면 00...0과 11...1도 만들 수 있다. 문자가 한 번만 바뀌는 경우에는 4, 5번째 행을 사용하고, 두 번 이상 바뀌는 경우에는 마지막 열에 닿지 않게 시작 행을 고르면 수정한 두 칸을 피할 수 있다.

N≤4N \leq 4N≤4에서는 칸이 최대 161616개뿐이므로 모든 격자를 확인하고 깊이 우선 탐색으로 필요한 경로를 찾는다. 전체 출력 경로 생성에는 O(NQ)O(NQ)O(NQ) 시간이 든다.