백준 1201번 NMK

문제 링크입니다: https://www.acmicpc.net/problem/1201

다음 주차 스터디에는 그리디 알고리즘(Greedy Algorithm)에 집중한다고 했는데 마침 슬랙에서 같은 학교 학우님이 질문하신 글을 보고 풀어본 문제였습니다.

여태까지 최대 부분 증가 수열, 최대 부분 감소 수열 관련된 문제는 무조건 DP로 풀었기 때문에 DP 문제인 것처럼 보였지만 사실 그리디 알고리즘을 적용해야 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 최대 증가 부분 수열과 최대 부분 감소 수열은 하나의 요소만 공유하기 때문에 N은 (M + K - 1) 이상이여하고 비둘기집 원리에 의해 숫자가 (M * K + 1)개일 때는 최대 증가 부분 수열의 길이는 M + 1, 최대 감소 부분 수열의 길이는 K + 1이 되기 때문에 N은 M * K 이하여야합니다.

2. 숫자를 1부터 N까지 오름차순으로 배열에 저장하고 최대 부분 증가 수열의 길이가 M이기 때문에 총 M개의 그룹으로 나눕니다. M개의 그룹으로 나눈 뒤 최대 부분 증가 수열의 길이가 M이 되도록 각 그룹을 역순으로 정렬합니다.

3. 각 그룹을 역순으로 정렬했기 때문에 최대 부분 감소 수열은 그룹 중 최대 길이임을 확인할 수 있습니다. 따라서 하나의 그룹은 K개의 숫자로 이루어져야합니다.

비둘기집 원리 참고

(https://ko.wikipedia.org/wiki/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N, M, K;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        cin >> N >> M >> K;

 

        //최대 부분 증가 수열과 최대 부분 감소 수열은 하나의 원소만 공유

        //N = M * K + 1인 경우: 길이가 M + 1인 증가 수열과 길이가 K + 1인 감소수열을 만들 수 있음

        if (M + K - 1 <= N && N <= M * K)

        {

                 vector<int> arr(N);

                 for (int i = 0; i < N; i++)

                         arr[i] = i + 1;

 

                 //하나의 그룹의 시작 인덱스

                 int idx = 0;

                 //M개의 그룹으로 나눈다

                 for (int i = 1; i <= M; i++)

                 {

                         //각 그룹에 들어있는 수는 K보다 작거나 같아야 하고

                         //주어진 조건을 만족시키기 위해서 한 그룹은 K개의 수를 같고 있다

                         int temp = min(idx + K, N - M + i);

                         //각 그룹을 뒤집어준다

                         reverse(arr.begin() + idx, arr.begin() + temp);

                         idx = temp;

                 }

 

                 for (int i = 0; i < N; i++)

                         cout << arr[i] << " ";

                 cout << "\n";

        }

        else

                 cout << -1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~