[PS | 문제 해설] BOJ 20921번 그렇고 그런 사이

 

안녕하세요,

이 글에서는 BOJ 의 20921번 그렇고 그런 사이 문제를 풀이하려고 합니다.

​

 

문제 정보는 아래 북마크를 통해 확인하실 수 있습니다.

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

20921번: 그렇고 그런 사이

 

해당 문제는

'1부터 n까지의 배열을,

배열에서 왼쪽에 있는 수가 오른쪽에 있는 수보다 큰 경우가

k개가 되도록 변형하는 문제'

로 요약할 수 있습니다.

​

 

예를 들어 k가 2인 경우, 왼쪽에 있는 배열은 오른쪽에 있는 배열로 바뀔 수 있습니다.

 

 

이때 오른쪽 배열에서, 왼쪽에 있는 수가 오른쪽에 있는 수보다 큰 경우를 찾아보면,

(3, 1), (3, 2)

로 2가지가 존재합니다.

​

 

문제를 이해하였으니,

다음으로 고민할 것은 '배열을 어떻게 바꾸어야 k개가 될 것인가'입니다.

 

 

저는 여기서 다음과 같은 특성을 이용하였습니다.

 

 

배열 [ 1, 2, 3, 4 ] 에서,

2보다 작은 원소는 1이므로, 왼쪽에 있는 2가 오른쪽에 있는 수보다 큰 경우는 최대 1가지입니다.

3보다 작은 원소는 1, 2이므로, 왼쪽에 있는 3이 오른쪽에 있는 수보다 큰 경우는 최대 2가지입니다.

4보다 작은 원소는 1, 2, 3이므로, 왼쪽에 있는 4가 오른쪽에 있는 수보다 큰 경우는 최대 3가지입니다.

​

 

이처럼 n을 다른 n-1개의 수보다 앞쪽으로 이동시킬 경우,

왼쪽에 있는 수가 오른쪽에 있는 수보다 큰 경우가 n-1개 발생합니다.

(n-1개의 수가 어떤 순서로 있더라도 성립합니다.)

​

 

따라서 만약 배열 [ 1, 2, 3, 4, 5 ] 이 주어지고 k가 7이라면,

5를 첫 번째 위치로 이동하여 원하는 경우가 4개 발생하도록 하고,

4를 두 번째 위치로 이동하여 원하는 경우가 3개 발생하도록 하여,

총 7개가 되도록 변형할 수 있습니다.

 

 

이를 토대로 다음과 같은 소스 코드를 작성하여 통과하였습니다.

 

#include <stdio.h>

#define MAX 4245 // 2 <= N <= 4242

int n, k, changed_num=0;
int original[MAX], changed[MAX]; // original : 원래 배열, changed : 변형한 배열

int main() {
    // 정수의 개수 n과 경우의 개수 k를 입력받는다.
    scanf("%d %d", &n, &k);

    // 원래 배열을 만든다. (만약 n이 5라면, 배열 { 1, 2, 3, 4, 5 } 을 만든다.)
    for (int i=0; i<n; i++)
        original[i] = i + 1;

    // i를 n-1부터 1로 줄여가면서, k가 i보다 크다면
    // k에서 i를 빼고 배열의 앞쪽에 i+1을 저장한다.
    // (이 과정을 통해 n=5이고 k=7이라면, k는 4+3으로 분해된다.)
    // (이와 동시에 i가 4일 때 배열의 첫 번째에 5가, i가 3일 때 배열의 두 번째에 4가 위치하게 된다.)
    // (그 결과 배열 original는 { 1, 2, 3, -1, -1 }이 되고, 배열 changed는 { 5, 4, ?, ?, ? }이 된다.)
    for (int i=n-1; i>0; i--) {
        if (k >= i) {
            k -= i;
            original[i] = -1;
            changed[changed_num++] = i+1;
        }
    }

    // 배열 changed를 앞에서부터 출력한다.
    // 이 때 배열 original에서 -1이 아닌 원소를 배열 changed에 차례대로 옮긴다.
    // (그 결과 배열 changed는 { 5, 4, 1, 2, 3 } 이 된다.)
    for (int i=0; i<n; i++) {
        if (original[i] >= 0)
            changed[changed_num++] = original[i];
        printf("%d ", changed[i]);
    }
    printf("\n");

    return 0;
}

 

다소 급하게 작성한 코드라, 이해가 어려우실까봐 걱정이 됩니다.

주석을 자세하게 달아놓았지만, 막히는 부분이 있다면 댓글로 얼마든지 질문해주세요.

 

​

감사합니다.