백준 1201 NMK Java

1부터 n까지의 수를 한번씩 이용해서

최대 부분 증가 수열의 길이는 m,

최대 부분 감소 수열의 길이가 k인

수열을 출력하면 되는 간단하지만 매우 어려운 문제이다.

dp 문제들 중 부분수열 문제를 복습하자.

 

이 문제는 dp로 푸는 것이 아닌 그리디 알고리즘 문제이다.

 

푸는 방법은 1~n까지의 수를 m등분 해서 

m등분 한 배열의 수 들을 뒤집으면 끝이다.

단 이 때 m등분한 배열의 길이 엔 k를 포함해야 한다.

 

예를 들어 13 5 4 를 입력 받으면

1 2 3 4 | 5 6 7 | 8 9 | 10 11 | 12 13

이런 식으로 m등분하고 m등분 한 배열의 길이 중 k를 포함하는 배열이 있어야 한다.

1부터 13을 5등분한 배열이며 1 2 3 4를 포함한 배열의 길이는 4이다.

이 배열을 각각 뒤집으면

4 3 2 1 | 7 6 5 | 9 8 | 11 10 | 13 12

k길이의 배열을 뒤집었을 때

길이가 4인 감소수열을 만들 수 있고

각각의 배열 중 아무런 수나 뽑아서 나열해보면 길이가 m인 증가수열을 만들 수 있다.

 

문제에서는 불가능한 경우엔 -1을 출력하라고 명시되어 있으므로

불가능한 조건을 알아보자.

 

불가능한 조건

1. 증가수열 m가 감소수열 k는 최대 1개의 정수를 공유할 수 있으므로

   m+k-1은 n보다 작거나 같아야 한다.

   n>=m+k-1

백준님의 강의자료 중,.

2. 길이가 k인 감소수열의 개수가 m개 있을 경우가 있다.

   6 2 3 으로 입력이 주어졌을 때

   3 2 1 / 6 5 4 처럼 길이가 3(m)인 감소수열이 2(k)개 있다.

   m이나 k가 +1만 되어도 불가능하다.

   n<=m*k

 

n>= m+k+1 && n<=m*k 의 조건에 위배되는 경우엔

-1를 출력한다.

 

1부터 n까지의 수를 m등분 하는 방법은 

group배열에 m등분할 경계를 넣는 것이다.

ArrayList<Integer> group = new ArrayList<Integer>(); //그룹의 경계를 넣을 배열
            group.add(0); //첫 시작은 무조건 0
            group.add(k); //일단 k를 넣는다.
            n -= k;
            m -= 1;
            int groupSize = (m == 0) ? 1 : n/m;
            int r = (m == 0) ? 0 : n%m;
            for (int i=0; i<m; i++) {
                int v = group.get(group.size()-1)+groupSize;
                if (r > 0) {
                    v++;
                    r -= 1;
                }
                group.add(v);
            }

첫 경계는 무조건 0이기 때문에 0을 넣는다.

무조건 k만큼은 등분해야 하므로 k도 넣는다.

0~k로 인해 1개의 배열이 생겼으므로 

m-1과 n에서 k를 빼고 m등분을 해야하므로

n-=k를 해준다.

그룹의 기본사이즈는 m이 0이 아니라면 n/m이고

int r 에는 n/m의 나머지를 저장해둔다.

for문에서는

그룹의 마지막 경계값에 m등분할 그룹들의 사이즈인 n/m을 더한다.

그리고 나머지가 있을 경우엔 +1을 해주고 r을 -1한다.

그룹에 넣어준다.

 

설명이 두서없지만 이렇게 그룹의 경계값들을 넣어주고

0부터 각각의 그룹의 경계값만큼 1~n을 저장해둔 배열에서

역순으로 뒤집어 주고 출력해주면 된다.

 

전체코드

public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        if (m+k-1 <= n && n <= m*k) { //불가능한 조건에 위배되지 않는 경우
            int[] a = new int[n];
            for (int i=0; i<n; i++) {
                a[i] = i+1;
            }
            ArrayList<Integer> group = new ArrayList<Integer>(); //그룹의 경계를 넣을 배열
            group.add(0); //첫 시작은 무조건 0
            group.add(k); //일단 k를 넣는다.
            n -= k;
            m -= 1;
            int groupSize = (m == 0) ? 1 : n/m;
            int r = (m == 0) ? 0 : n%m;
            for (int i=0; i<m; i++) {
                int v = group.get(group.size()-1)+groupSize;
                if (r > 0) {
                    v++;
                    r -= 1;
                }
                group.add(v);
            }
 
            for (int i=0; i<group.size()-1; i++) {
                int begin = group.get(i);
                int end = group.get(i+1)-1;
                while (begin < end) {
                    int temp = a[begin];
                    a[begin] = a[end];
                    a[end] = temp;
                    begin += 1;
                    end -= 1;
                }
            }
            for (int i=0; i<a.length; i++) {
                System.out.print(a[i] + " ");
            }
        } else {
            System.out.println(-1);
        }
    }

너무너무 어렵다.