[Jungol] 정올 3031 인형정리

출처: [Jungol] 정올 3031 인형정리

 Input 

7 2

1

2

2

2

1

2

1

 

 Output 

2 

먼저 놓여있는 인형의 종류는 2종류이고 왼쪽에서 오른쪽으로 1, 2, 2, 2, 1, 2, 1로 7개의 인형이 진열되어 있다.

같은 종류끼리 정렬하는데 꺼낸 인형의 개수를 최소화하려면

왼쪽에서 1 번째와 6 번째 인형을 꺼내 왼쪽에서 1 번째로 유형 2의 인형을 왼쪽에서 6 번째로 유형 1의 인형을 배치한다.

이 때 꺼낸 인형의 개수는 2 개이다. 

 Input 

12 4

1

3

2

4

2

1

2

3

1

1

3

4

 

 Output 

7

O (M! * N)

DFS 탐색을 통해서 인형 종류의 순서를 결정합니다.

M 종류의 인형을 종류별로 배치하는 경우의 수 = M!

ex) 1, 2, 3 → [1 2 3], [1 3 2], [2 1 3], [2 3 1], [3 1 2], [3 2 1] ▶ DFS 탐색

 

인형 종류 배치 순서가 정해졌을 때, 필요한 교환 횟수

[1  3  2  4  2  1  2  3  1  1  3  4] → 숫자별 나타난 횟수: 『1』 = 4개, 『2』 = 3개, 『3』 = 3개,  『4』 = 2개

if) [3 2 1 4] 종류로 배치하는 경우 → [3 3 3] + [2 2 2] + [1 1 1 1] + [4 4]로 배치됩니다.

    따라서 input으로 [1  3  2  4  2  1  2  3  1  1  3  4]가 주어졌으므로 종류별로 교환해야 하는 인형을 찾을 수 있습니다.

    [1  3  2]  + [4  2  1] + [2 3  1  1] + [3  4] → 빨갛게 표시된 숫자들에 한해서 자리 교환이 필요합니다.

    ※ 실제 해당 숫자들이 어느 숫자와 교환되는지에 따라 교환횟수가 다를 수 있지만 최적의 교환횟수는

        정해진 인형 종류 배치 순서에 해당되는 위치로 이동해야 하며 이와 관련해서는 고려하지 않습니다.

 → 즉, 정해진 인형 종류 배치에서 각 종류에 해당하지 않는 인형의 개수를 찾으면 됩니다.

    ex) 인형 종류 3이 4개 배치되어야 하는 위치(그룹)에 [3 3 2 1]이 있다면 2번의 교환이 필요합니다.

#include <stdio.h>
const int MAX_N = 1e5;
const int MAX_M = 10;
int N, M, ans;
int doll[MAX_N + 10], visited[MAX_M + 10], dollCnt[MAX_M + 10];
 
void input() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &doll[i]);
    }
}
 
int calMoveCnt(int s, int id) {
    int cnt = 0;
    for (int i = 0; i < dollCnt[id]; i++) {
        if (doll[s + i] != id) cnt++;
    }
    return cnt;
}
 
void DFS(int idx, int s, int swapCnt) {
    // 이미 구한 값(ans)보다 필요한 교환횟수가 많은 경우 중단(분기한정)
    if (ans <= swapCnt)
        return;
 
    // M 종류 배치가 완료된 경우
    if (idx > M) {
        ans = swapCnt;
        return;
    }
 
    for (int i = 1; i <= M; i++) {
        if (visited[i] == 1) continue;
        visited[i] = 1;
        // 인형 종류 순서가 정해진대로 필요한 교환횟수 확인
        int needCnt = calMoveCnt(s, i);
        // 인형 종류 순서, 인형이 놓이기 시작하는 위치, 교환 횟수
        DFS(idx + 1, s + dollCnt[i], swapCnt + needCnt);
        visited[i] = 0;
    }
}
 
int solve() {
    // 인형 종류별 개수
    for (int i = 1; i <= N; i++) {
        dollCnt[doll[i]]++;
    }
    // 인형을 최대 많이 옮기는 경우
    ans = N;
    // 인형 종류 순서, 인형이 놓이기 시작하는 위치, 교환 횟수
    DFS(1, 1, 0);
    return ans;
}
 
int main() {
    input();
    printf("%d\n", solve());
}

O(M!)

인형 종류가 결정되었을 때, 필요한 교환횟수를 부분합(psum[][])을 통해 빠르게 구할 수 있습니다.

인형 종류별 psum[][]을 구합니다. (psum[i][j] = 종류 i 인형이 1~j번째 위치까지 존재하는 인형개수)

ex) psum[4][9] = 종류 4인 인형이 1~9번째 위치까지 존재하는 인형은 총 1개

     → 위치 [6, 9]에서 종류 4 인형의 개수는? → psum[4][9] - psum[4][6-1] = 1 - 1 = 0

          [1  3  2  4  2  1  2  3  1  1  3  4]

ex) [1  3  2  4  2  1  2  3  1  1  3  4]에서 종류를 [3 4 1 2]로 배치했을 때 종류 4에서 필요한 교환횟수는?

     (앞선 종류 3은 [3 3 3]이 배치가 완료된 상태라고 가정) 인형 종류 『4』의 개수는 2개

     4~5번째에 인형 종류 『4』가 있는 개수는 psum[4][5] - psum[4][3] = 1  → 필요한 교환 횟수 = 2 - 1

 

ex) [1  3  2  4  2  1  2  3  1  1  3  4]에서 종류를 [3 4 1 2]로 배치했을 때 종류 2에서 필요한 교환횟수는?

     (앞선 종류 3, 4, 1은 [3 3 3 4 4 1 1 1 1]로 배치가 완료된 상태라고 가정) 인형 종류 『2』의 개수는 3개

     10~12번째에 인형 종류 『2』가 있는 개수는 psum[2][12] - psum[2][9] = 0  → 필요한 교환 횟수 = 3 - 0 = 3

 

ex) [1  3  2  4  2  1  2  3  1  1  3  4]에서 종류를 [1 2 3 4]로 배치했을 때 종류 3에서 필요한 교환횟수는?

     (앞선 종류 1, 2는 [1 1 1 1 2 2 2]로 배치가 완료된 상태라고 가정) 인형 종류 『3』의 개수는 3개

     8~10번째에 인형 종류 『3』이 있는 개수는 psum[3][10] - psum[3][7] = 1  → 필요한 교환 횟수 = 3 - 1 = 2

▶ 인형 종류 순서(DFS)가 정해지고 psum[][]배열이 준비된 상태에서,

    해당 종류의 인형이 시작되는 위치와, 해당 종류의 인형 개수 정보(dollCnt[]) 이용

#include <stdio.h>
const int MAX_N = 1e5;
const int MAX_M = 10;
int N, M, ans;
int doll[MAX_N + 10], visited[MAX_M + 10], dollCnt[MAX_M + 10];
int psum[MAX_M + 10][MAX_N + 10];
 
void input() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &doll[i]);
    }
}
 
void DFS(int idx, int s, int swapCnt) {
    // 이미 구한 값(ans)보다 필요한 교환횟수가 많은 경우 중단(분기한정)
    if (ans <= swapCnt)
        return;
 
    if (idx > M) {
        ans = swapCnt;
        return;
    }
 
    for (int i = 1; i <= M; i++) {
        if (visited[i] == 1) 
            continue;
 
        visited[i] = 1;
        int needCnt = dollCnt[i] - (psum[i][s + dollCnt[i] - 1] - psum[i][s - 1]);
        DFS(idx + 1, s + dollCnt[i], swapCnt + needCnt);
        visited[i] = 0;
    }
}
int solve() {
    // 인형 종류별 개수
    for (int i = 1; i <= N; i++) {
        dollCnt[doll[i]]++;
        psum[doll[i]][i] = 1;
    }
 
    // 종류별 구간합 구하기
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            psum[i][j] += psum[i][j - 1];
        }
    }
    ans = N;
    // 인형 종류 순서, 인형이 놓이기 시작하는 위치, 교환 횟수
    DFS(1, 1, 0);
    return ans;
}
int main() {
    input();
    printf("%d\n", solve());
}