알고리즘 풀이 - 백준 1201(NMK, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

1~N 수를 한 번씩 이용해서 LIS와 길이가 M이고, LDS의 길이가 K인 수열을 구하는 문제

 

 

2. 풀이

 

이 문제는 난이도가 높아 풀기가 꽤 어렵다.

우선, M, K의 길이로 LIS / LDS를 하나의 수열에서 만들어야 하는데 M과 K가 어떻게 주어지느냐에 따라 만들 수 있거나 만들 수 없는 경우가 있다. 그 조건부터 살펴보자.

결론부터 말하자면 그 조건은 다음과 같다.

$M+K-1 \leq N \leq  M*K$

 

우선 좌측 조건 부터 살펴보자. 

왜 N이 M+K-1보다 크거나 같아야 할까? 이 부분은 M과 K 길이를 지정했을 때, 가장 그 값을 최대한 크게 지정한 것보다는 N이 커야 한다는 의미이다.

즉, 최소 M개의 수는 증가수열에, 최소 K개의 수는 감소수열에 포함되어야 하는데, 이를 최대로 하는 경우는 모든 수가 연속적으로 각각의 증가수열 혹은 감소수열에 반드시 포함되도록 하는 경우일 것이다.

예를 들어 N = 9라면, M과 K는 (9, 0) / (8, 1) / (7, 2) / ... / (2, 7) / (1, 8), (0, 9) 중 하나라고 할 때, 그 경우에는 N개의 모든 수열이 연속적으로 증가수열 혹은 감소수열에 반드시 있어야 한다는 의미이다.

 

M과 K가 (5, 5)라면 아래와 같은 예시가 정답일 것이다.

즉, 연속적으로 모든 수를 이용해 증가 또는 감소 수열에 포함시키지 않으면 최대한 모든 것을 다 이용하여 LIS / LDS를 만들 수 없다.

 

그런데, 연속하여 증가 / 감소 수열을 만들면, 증가 / 감소 수열에서는 반드시 1개의 수를 공유하게 되므로 이 범위보다는 N이 크거나 같아야 한다.

 

 

그리오 우측 조건을 알아보자.

N은 MxK 보다 작거나 같아야 한다. 이 부분은 크기가 K인 내림차순 수열이 M개 있을 수 있으므로 N이 너무 크면 그 경우를 만들 수 없다는 뜻이다.

위의 N = 9일 때를 예시로 보고 M, K를 (3, 3)으로 해서 보자.

그렇다면, 이 뜻은 3개의 수를 내림차순으로 갖는 M개의 수열이 있다는 의미다. 그러면 아래와 같은 경우가 답이 될 수 있다.

점선으로 갈라진 각각의 부분 수열은 내림차순이고 각각의 가장 첫번째 혹은 두번째, 마지막 숫자끼리만 잇게 되면 오름차순 수열을 만들 수 있다.

 

하지만 이 때, MxK + 1의 숫자와 N이 같다고 한다면, 비둘기집 원리에 따라 크기가 M+1개인 증가수열 또는 K+1개인 감소수열을 반드시 만들 수 있게 된다.

왜냐하면, 수의 크기가 K개인 수열이 최대 M개 있는데, 남은 하나를 반드시 어딘가에는 넣어줘야 하기 때문에, 그로인해 증가수열 혹은 감소수열의 크기가 1 더 생기게 되어 불가능한 경우가 되기 때문이다.

 

따라서 위의 두 조건에 부합하지 않도록 N, M, K가 주어진다면 -1을 출력하면 된다.

 

위 범위에 부합한다면, 우리는 우측 조건을 설명할 때 말한 것과 같은 방식으로 문제를 풀 수 있다.

즉, 최대 K개의 숫자를 내림차순으로 갖는 수열을 M개 만들면 되는 것이다.

 

예를 들어, N=9, M=3, K=4로 주어졌다고 하자. 그러면 이는 위의 조건에 부합하는 경우이다. 이 정답은 다음과 같은 경우 답이 될 수 있다.

 

 

위의 정답은 어떻게 만들 수 있을까? 

우선 첫번째 그룹은 반드시 K개의 숫자로 이루어진 그룹으로 만들어야 한다. 그러면 추가로 만들어야 하는 최대 4(K)개의 수를 내림차순으로 갖는 그룹은 2(M-1)개가 된다.

숫자 N개 중 4개는 이미 사용 완료이므로 N-4=5가 된다.

 

그러면, 숫자 5개를 최대 4개의 수를 내림차순으로 갖는 2개의 그룹으로 나누어야 한다.

 

이 때, 숫자 5개를 2개의 그룹으로 나누기 때문에, 5 나누기 2(5 / 2)를 하면 몫이 2, 나머지가 1이 될 것이다.

즉, 숫자 2개로 이루어진 내림차순 수열 그룹 2개를 만들면 이용해야 하는 숫자가 1개 남는다는 의미이다.

 

나머지 값은 제수(나누는 수, 즉 여기서는 2)보다 절대 클 수 없기 때문에 나머지가 0이 될 때까지 각 그룹에 1개씩 추가 할당을 하면 문제를 해결할 수 있다.

즉, 그러면 그룹 2개는 숫자 3개, 2개로 이루어진 내림차순 수열이 되는 것이다.

 

이를 코드로 작성하여 문제를 해결해보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] nums = new int[n];
        for(int i=0; i < n; i++){
            nums[i] = i+1;
        }
        
        // 최소범위 : M+K-1
        // 최대범위 : MK
        if(n < m+k-1 || m*k < n) {
            System.out.println(-1);
            return;
        }
        
        // 그룹을 맺을 start / end 부분을 저장하는 list
        Deque<Integer> list = new LinkedList<>();
        
        // 처음에는 0부터 k-1까지 저장해야 하므로 0과 k를 각각 start / end로 지정한다.
        list.offer(0); list.offer(k);
        n -= k;  // k개의 데이터는 사용 완료이므로 k를 뺀다.
        m -= 1;  // 1개의 그룹이 생성되었으므로 1을 뺀다.
        
        // 1개의 그룹을 만들었으니 나머지 그룹을 만들기 위해 필요한 크기를 구한다.
        // m == 0이면 추가 필요 그룹이 없으니 0으로 지정한다.
        // 0이 아니면 n/m 만큼의 크기로 그룹을 만들어야 한다.
        int groupSize = m == 0 ? 0 : n/m;
        
        // 나머지 값이 있다면 그 수만큼 다른 그룹에 +1씩해서 나누면 된다.
        int r = m == 0 ? 0 : n%m;
        
        // 그룹의 End부분을 계속 넣는다.
        for(int i=0; i < m; i++){
            list.offer(list.getLast() + groupSize + (r > 0 ? 1 : 0));
            if(r > 0) r--;  // 나머지가 아직 남아있으면 빼준다.
        }
        
        StringBuilder sb = new StringBuilder();
        
        // start, end값을 빼서 내부 배열의 값을 모두 반전시킨다.
        int start = 0; int end = list.pollFirst();
        while(!list.isEmpty()){
            start = end;
            end = list.pollFirst();
            
            // end-1부터 start까지 reverse하여 붙힌다.
            for(int j=end-1; j >= start; j--){
                sb.append(nums[j]).append(" ");
            }
        }
        
        System.out.println(sb);
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.