https://www.acmicpc.net/problem/1201

💡 접근방법

이 문제는 아이디어를 떠올리는 것이 중요하다, 1 ~ N까지 나열된 수열을 생각해보자

M개의 오름차순을 만들어야 한다. 1 ~ N까지 나열된 수들을 최대한 유지하면서 만들 수 있을까? M개 그룹을 나눠서, 그룹 내에서 한 숫자씩 뽑으면 M개의 오름차순을 만들 수 있다.

하지만, 그룹 내에서 한 숫자씩 뽑는 건 문제가 원하는 것이 아니다.

그룹의 모든 숫자들을 역순시키면, 그룹 내에서 한 숫자씩 뽑아서 M개의 오름 차순을 만드는건 유효하다.

K개의 내림차순은 어떻게 만들까?

그룹을 역순한 결과를 보면, 그룹 개수가 K개가 된다면 K개의 내림차순이 존재할수 있다.

그룹내에 K개가 들어가게 하는 것은 쉬운데, 어떻게 M개의 그룹을 보장시켜줄수 있을까?

N = 13, M =5, K = 4인 문제를 이해해보자. 여기서 최대 K개를 가질 수 있도록 그룹을 만들어준다.

1 ~ 4까지 1개의 그룹을 만들었다.

5 ~ 8까지 1개의 그룹을 만들었다.

9 ~ 12까지 1개의 그룹을 만들었지만, 문제가 발생했다. M개의 그룹을 만들어야 하는데, 현재 나머지 것을 포함한다고 해도 M개를 만들 수 없다.

M개를 만들기 위해서는, 9 ~ 11까지 1개의 그룹을 만들도록 해야 한다.

K개를 선택할지 OR K개보다 작은 수를 선택해서 M개의 그룹을 만들지 결정

계속 K개를 가진 그룹들을 만들면 원하는 M개의 그룹을 만들지 못한다. K개를 가진 그룹들을 만드는 것을 멈춰야 하는 순간이 존재한다.

K개 숫자를 가진 그룹을 만드는 것을 멈춰야 하는 순간?

i번째 그룹의 마지막 수를 가리키는 인덱스가 N - M + i 인덱스보다 커지는 순간 멈춰야 한다. N - M + i + 1인덱스는 1개 숫자를 가진 그룹 M - i개를 만들 수 있는 시작 인덱스이다.

N - M + i 인덱스보다 큰 값이 선택되면 어떻게 될까?

1개씩 담을 수 있는 최대 개수인 M - i보다 작아지므로, 현재 만들어진 i개의 그룹에서 M - i - @를 더하면 M - @이므로 M보다 작아질 수 밖에 없다.

💡 해설코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static void rotate(int[] arr, int start, int end){
		while(start < end){
			int tmp = arr[start];
			arr[start] = arr[end];
			arr[end] = tmp;
			
			start++;
			end--;
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] sArr = br.readLine().split(" ");
		int[] arr;
		
		int N, M, K;
		
		N = Integer.valueOf(sArr[0]);
		M = Integer.valueOf(sArr[1]);
		K = Integer.valueOf(sArr[2]);
		
		arr = new int[N + 1];
		for(int i = 1; i <= N; i++) arr[i] = i;
		
		if(!((M - 1) <= (N - K) && (N - K) <= K * (M - 1))){
			System.out.println("-1");
			return;
		}
	
		int idx = 1;
		for(int i = 1; i <= M; i++){
			int tmp = Math.min(idx + K, (N + 1) - M + i);
			rotate(arr, idx, tmp - 1);
			if(tmp != idx + K) break;
			idx = tmp;
		}
	
		for(int i = 1; i < arr.length; i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}
}