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

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

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

격자 정렬

문제로 돌아가기

해설

홀수 행은 왼쪽에서 오른쪽, 짝수 행은 오른쪽에서 왼쪽으로 읽어 길이 K=N2K=N^2K=N2의 뱀 모양 경로를 만든다. 이 경로에서 이웃한 두 칸은 실제 격자에서도 인접한다.

경로를 일차원 배열로 보고, 길이를 하나씩 줄이는 버블 정렬 비교를 모두 출력한다. 값은 읽을 필요가 없고, 각 비교·교환은 허용된 연산 하나로 구현된다. 오른쪽으로 이동하는 경로 간선은 종류 222, 아래로 이동하는 간선은 종류 111, 왼쪽으로 이동하는 간선은 종류 444를 사용한다. 왼쪽 이동에서는 연산의 좌표를 왼쪽 칸으로 지정해야 한다.

첫 단계는 K(K−1)/2K(K-1)/2K(K−1)/2개의 연산으로 경로를 오름차순 정렬한다. 각 행에는 이미 그 행에 들어가야 하는 값들만 있지만, 짝수 행의 순서는 거꾸로 되어 있다. 모든 짝수 행을 종류 222의 버블 정렬로 정렬한다.

총 연산 수는

X=N2(N2−1)2+⌊N2⌋N(N−1)2≤N42+N34≤N4.X=\frac{N^2(N^2-1)}2+\left\lfloor\frac N2\right\rfloor\frac{N(N-1)}2\leq\frac{N^4}{2}+\frac{N^3}{4}\leq N^4.X=2N2(

출력 시간은 O(N4)O(N^4)O(N4), 경로 저장 공간은 O(N2)O(N^2)O(N2)이다. N=30N=30N=에서 이다. 이고, 채점 반복 횟수의 분자는 이다. 모든 계산은 64비트 정수 범위 안에 들어간다.

서브태스크 1의 단순 구현은 뱀 경로 전체를 KKK번 반복해서 버블 정렬한다. 이후 짝수 행을 정렬하면 N=2,3,4N=2,3,4N=2,3,4에서 각각 13,75,25213,75,25213,75,252개 연산이므로 제한을 만족한다. 전체 범위에서는 이미 확정된 끝부분을 제외하여 첫 단계의 비교 수를 K(K−1)/2K(K-1)/2로 줄여야 한다.

체커는 연산을 O(X)O(X)O(X) 공간에 저장한다. O(⌊108/N4⌋(N2+X))O(\lfloor10^8/N^4\rfloor(N^2+X))O(⌊108/N4⌋(N 시간에 검사한다.

Solution written by GPT6

N
2
−
1
)
​
+
⌊2N​⌋2N(N−1)​≤
2N4​+
4N3​≤
N4.
30
X=411 075X=411\,075X=411075
N4≤810 000N^4\leq810\,000N4≤810000
10810^8108
K(K−
1)/2
2
+
X))