[백준][C++] 20036번 Ball Alignment (dp)

1. 문제

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

 

 

-> 

 

- 중력에 의하여 공하나를 제거할 시 공들은 중간으로 모이게 된다.

 

- 그리고 뺀 공은 맨 왼쪽이나 맨 오른쪽에만 넣을 수 있다.

 

- 이때 공을 빼는 최소 횟수를 구해야한다.

 

 

2. 풀이

 

- 먼저 같은 공을 두번이상 손을 대지 않는다는것을 눈치채야한다.

  (첫번째 공을 뺀 행동의 의미가 없어짐, 그러므로 1번 공을 빼는것이 최소가 된다.)

 

- 한 공마다 최대 1번만 공을 건들 수 있으므로

 

- 적절히 공을 제거해줘야하는데, 

 

- 중간에 삽입 불가능하므로

 

- 나머지 공들을 "정렬된 부분"으로 만드는 방향으로 제거해줘야한다.

 

- 그러므로 이 문제는 주어진 배열에서 가장 긴 정렬된 부분 수열을 구하는 문제로 변형할 수 있다.

 

가장 간단한 예

ex) 1, 2, 3, 4, 6, 5

- 1 : 1, 2, 3, 4, 5

- 2 : 2, 3, 4, 5

- 3 : 3, 4, 5

- 4 : 4, 5

- 5 : 5

- 6 : 6

=> 6 - 5 : 1개의 공만 빼서 정렬 가능하다.

 

ex) 2 1 2 1 2 1 2 3

- 1: 1, 1, 1, 2 

- 2: 2, 2, 2, 2, 3

- 3: 3

=> 8 - 5 : 3개의 공만 빼서 정렬가능하다

 

2.1 동적 계획법

- 일단 같은 공이 몇개라도 올 수 있으므로 주어진 배열을 map에 담고 정렬시킨다.

 

- 여기서 map의 key 는 공의 번호이고, value 는 인덱스들의 번호이다.

 

- 같은 원소가 있을 시 맨 앞에 있는 원소를 가지고 더 긴 증가부분수열을 만들 수 있으므로

 

- 각 원소의 첫번째 인덱스만 조사할 것이다. 

    for (auto it = dic.begin(); it != dic.end(); it++)
    {
        int idx = it->second[0];
        int length = dp(idx, idx, it, 1);
        answer = min(answer, static_cast<int>(bs.size()) - length);
    }

 

- dp는 메모이제이션을 활용하여 idx에서 시작하는 가장 긴 정렬된 연속 수열의 길이를 리턴한다.

- dp의 root 는 수열이 시작하는 인덱스이며

- idx는 현재 조사하고있는 수열의 위치이고

- is_root는 현재 idx가 root와 같은 값인지를 나타낸다.

 

- cached는 idx 와 is_root를 메모하여,

- idx에서부터 해당 idx가 루트와 같은 값 일때의 최장정렬연속부분수열의 길이와

- idx에서부터 해당 idx가 루트와 같은 값이 아닐때의 최장정렬연속부분수열의 길이를 저장한다.

 

- 이때 root와 같은 값인지 메모이제이션해야하는 이유는

- root와 같은 원소들은 왼쪽에 삽입가능하기 때문에 "스킵" 가능하지만

- 그 이후로 오는 root와 값이 같지 않은 원소들은 동일한 모든 원소가 전부 포함되어있어야한다.

 

이를 함수로 나타낸게 dp 이며 대략 두개의 부분문제로 나누어진다.

• 같은 값의 다음으로 갈 수 있는 인덱스 : dic[bs[idx]] 안에서 idx 다음의 인덱스에서의 최장길이 + 1
• 다음값에서 해당 idx보다 큰 idx : it++ 하여 다음값 dic[next] 안에서의 idx 다음의 인덱스에서의 최장길이 + 1

이런 dp함수를 통해 최장정렬연속부분수열을 구할 수 있으며 전체 공들의 개수에서 빼주면

공을 빼는 최소 횟수를 구할 수 있다.

 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;

vector<int> bs;
map<int, vector<int>> dic;
int n, t;

int cached[100001][2];

int dp(int root, int idx, map<int, vector<int>>::iterator it, int same_count)
{
    int &ret = cached[idx][bs[root] == bs[idx]];
    if (ret == -1)
    {
        ret = 1;
        int value = bs[idx];
        int idx_lo = lower_bound(dic[value].begin(), dic[value].end(), idx) - dic[value].begin();
        // same value test
        if (idx_lo + 1 < (int)dic[value].size())
        {
            ret = max(ret, dp(root, dic[value][idx_lo + 1], it, same_count + 1) + 1);
        }
        it++;
        // next value
        if (it != dic.end() && (bs[root] == value || (bs[root] != value && same_count == (int)dic[value].size())))
        {
            int n_f_idx = it->second[0];
            int n_value = bs[n_f_idx];
            int n_idx_lo = lower_bound(dic[n_value].begin(), dic[n_value].end(), idx) - dic[n_value].begin();
            if (n_idx_lo < (int)dic[n_value].size())
            {
                ret = max(ret, dp(root, dic[n_value][n_idx_lo], it, 1) + 1);
            }
        }
    }
    return ret;
}

int solve()
{
    int answer = bs.size();

    for (auto it = dic.begin(); it != dic.end(); it++)
    {
        int idx = it->second[0];
        int length = dp(idx, idx, it, 1);
        answer = min(answer, static_cast<int>(bs.size()) - length);
    }
    return answer;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //   freopen("input.txt", "r", stdin);

    cin >> n;
    bs.resize(n);
    dic.clear();
    memset(cached, -1, sizeof cached);
    for (int i = 0; i < n; i++)
    {
        cin >> bs[i];
        dic[bs[i]].push_back(i);
    }
    cout << solve() << "\n";
}

 

 

5. 다른 풀이

https://www.acmicpc.net/user/edenooo 님의 풀이

https://www.acmicpc.net/source/23220295