N = int(input())
seq = [*map(int,input().split())]
S = []; MAX = 0
for i in range(N):
if MAX==i:
S.append([])
n = seq[i]
MAX = max(MAX,n)
S[-1].append(i+1)
print(len(S))
for s in S:
print(len(s),*s)비둘기집 원리를 이용하여 해결하였다.
아이디어를 떠올리기 쉽지 않았던 문제였다. 디지털 비디오 디스크 [백준 9345번] 디지털 비디오 디스크(DVDs) (Python3) (tistory.com) 문제처럼 숫자가 1~N까지 한개씩 있다는 것에 주의해야 하는데, 저 문제에서 내가 생각한 풀이와 다르게 비둘기집을 이용한 풀이가 있다는 것을 공부한 경험이 아이디어를 떠올리는데 도움이 되었다.
비둘기집 원리에 의하여 M번째 숫자까지 체크했을 때 만약 최댓값이 M이면, 그 앞의 모든 숫자들은 1~M을 이룬다는 뜻이 된다. 따라서 지문의 규칙에 의해 그래프를 더 이상 형성할 수 없고 (다음에 나오는 숫자들은 무조건 M보다 크기 때문), 새로운 집합을 만들어주게 된다.
이를 이용하면 구현은 쉽게 할 수 있다.
여담) 이 문제 숏코딩 순위 1위가 되었다.
