[백준] 1201번 NMK - Python / 알고리즘 중급 1/3 - 그리디 알고리즘 (도전)

ByungJik_Oh·2025년 6월 19일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

171/244

💡 문제

1부터 N까지의 수를 한 번씩 이용해서 가장 긴 증가하는 부분 수열의 길이가 M이고, 가장 긴 감소하는 부분 수열의 길이가 K인 수열을 출력한다.

입력

첫째 줄에 세 정수 N, M, K가 주어진다.

출력

첫째 줄에 문제의 조건을 만족하는 수열을 출력한다. 만약, 조건을 만족하는 수열이 없다면 -1을 출력한다.

💭 접근

이 문제를 이해하기 위해 단순한 예를 들어 보자. 입력이 n = 6, m = 2, k = 3으로 주어졌다고 했을 때, 길이가 3인 감소하는 부분 수열(LDS)을 2개로 만들어 붙여 길이가 2인 증가하는 부분수열(LIS)을 만들 수 있는데, 이때 첫번째 오는 LDS의 원소들은 반드시 두번째 오는 LDS의 원소들 보다 작아야만 한다. 쉽게 말하자면 여러 개의 LDS를 만든 뒤, 각 LDS를 하나의 원소로 간주하고 LIS를 만드는 것이다.

입력 (n = 6, m = 2, k = 3)를 순서대로 해결해 보자.

먼저 m * k크기의 0으로 이루어진 배열을 만든다.
ans = [0, 0, 0, 0, 0, 0]
이후 두개의 LDS를 만들어 붙인다.
ans = [4, 3, 1, 6, 5, 2]

이처럼 [4, 3, 1]과 [6, 5, 2] LDS를 만들어 길이가 2인 LIS를 구성한 것을 볼 수 있다.
그렇다면 이 작은 LDS들은 어떤 규칙으로 만들 수 있을까?

먼저 주어진 k와 m의 곱 만큼의 0으로 이루어진 리스트를 생성한다.
ans = [0, 0, 0, 0, 0, 0]

이후 k 만큼의 간격으로 1부터 오름차 순으로 수를 채운다.
ans = [0, 0, 1, 0, 0, 2]

이제 2개의 LDS를 구성할 차례이다. 이때 LDS를 구성하기 위해서는 하나의 규칙이 있었는데 첫번째 LDS의 원소들은 두번째 LDS의 원소보다 반드시 작아야 한다는 것이다. 그리고 각각의 LDS는 길이가 3이다. 이렇게 구성하기 위해서는 맨 끝 LDS부터 큰 수로 채우고, 남는 수를 첫번째 LDS에 채우는 것이다.
ans = [0, 0, 1, 6, 5, 2] -> ans = [4, 3, 1, 6, 5, 2]

위와 같은 방법으로 수열을 구성하면 입력에서 주어진 조건에 맞는 수열을 구성할 수 있다.
그렇다면 수열을 구성할 수 없는 경우는 어떤 경우가 있을까?

위에서 수열을 구성할 때 보았던 것처럼 m * k가 n보다 작을 때는 수열을 구성할 수 없다.
만약 n = 6, m = 2, k = 2인 경우를 생각해보자. 애초에 m * k 크기의 0으로 이루어진 배열을 생성하면 크기가 4인 리스트가 생성되는데 이미 길이가 총 6인 수열을 구성할 수 없게 되기 때문이다.

또한 한가지 경우가 더 있는데, 맨 끝 LDS를 구성하지 못할 때 발생한다.
만약 n = 3, m = 2, k = 3 으로 입력이 주어졌다고 했을 때 다음과 같다.

ans = [0, 0, 1, 3, 0, 2]

이처럼 맨 끝 LDS를 완성시키지 못한다면 (하나의 LDS도 만들지 못한다면) 길이가 k인 LDS를 절대 만들 수 없게 된다.

따라서 위처럼 수열을 구성할 수 없는 입력만 잘 구분해 낸다면 해결하는 데에 큰 어려움이 없었던 문제였다.

📒 코드

n, m, k = map(int, input().split())
ans = [0 for _ in range(m * k)]
num = [i for i in range(1, n + 1)]

if len(ans) < n:
    print(-1)
else:
    for i in range(k - 1, m * k, k):
        ans[i] = num.pop(0)
        # print(ans) n = 13, m = 5, k = 4 일 때
        # 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5
    if k != 1 and not num:
        print(-1)
    else:
        cursor = m - 1
        while num:
            for i in range(k * cursor, k * (cursor + 1) - 1):
                if num:
                    ans[i] = num.pop()
                    # print(ans) n = 13, m = 5, k = 4 일 때
                    # 0 0 0 1 0 0 0 2 7 6 0 3 10 9 8 4 13 12 11 5
                    last_index = i

            if cursor == m - 1 and ans[last_index + 1] == 0:
                print(-1)
                break
            cursor -= 1
        else:
            for i in ans:
                if i != 0:
                    print(i, end=' ')