COFO::1415C Bouncing Ball

• Link : COFO::1415C

Problem

• level : 1400
• tag : brute force, dp, implementation
• 아이디어가 어렴풋이 떠올랐을때 이걸 어떻게 코드로 표현할지, 복잡도가 정확히 in time 가능한지에 대해 생각해보았고,
• 이게 이렇게 하면 시간내에 충분히 돌겠다 라는 확신을 가지는 순간 PS가 주는 쾌감이 있는 것 같은 문제였습니다.

Point

• n 개의 박스로 이루어진 string s 가 주어집니다.
  • 박스가 비어있는 곳은 0, 존재하는 곳은 1로 표시합니다.
• 공을 떨어뜨리는 첫번째 위치는 앞에서부터 p번째 박스이며, 공은 k칸만큼 바운스됩니다.
• 이때 사용할 수 있는 2가지 작업이 있습니다.
  • x초가 소모되는 작업은, 비어있는 i번째 박스를 채우는 것입니다.
  • y초가 소모되는 작업은, 맨 앞 인덱스에있는 박스를 통째로 제거해서 인덱스를 모두 하나씩 늘리는 방법입니다.
• 위의 작업을 사용해서, 최소의 초가 소모되도록 공을 바운스 시킵니다.
  • 단, 공이 바운스되는 박스는 항상 채워져있어야 하며, 박스는 최소 p개 존재해야합니다.

Design

• 매우 복잡해보이지만, x, y 작업 몇개를 해보면 규칙을 찾을 수 있습니다.
• 그 규칙은 다음과 같습니다.
  • 공이 k칸씩 바운스됩니다.
  • 즉, 앞에 박스가 몇개가 없어졌건 k칸씩 바운스 된다는 의미입니다.
• 위의 정보를 이용해서 다음과 같은 방법으로 문제를 해결할 수 있습니다.
  • p번째에 공이 첫번째로 튀기는 집합
  • p+1번째에 공이 첫번째로 튀기는 집합(이때는 맨 앞 하나를 제거한다는 의미)
  • p+2번째에 공이 첫번째로 튀기는 집합(이때는 맨 앞 두개를 제거한다는 의미)
  • …
  • p+k번째에 공이 첫번째로 튀기는 집합(이때는 맨 앞 k개를 제거한다는 의미)
• 다행히도 p+k까지만 생각하면 됩니다.
  • p+k+1번째의 경우, p번째에 공이 첫번째로 튀기는 것에 포함된 집합이기때문입니다.
  • 이때, 앞의 k개만 제거해주면 같은 집합이 되겠지요
• 결국, 총 k개의 집합이 존재합니다.
• 각 집합에서 공이 바운스되는 위치는 정해져있습니다.
  • 즉, 01110 처럼 해당 집합의 원소들을 나열할 수 있습니다.
  • 해당 집합에 포함된 0과 1의 갯수를 모두 세어주는 작업을 먼저 진행합니다.
  • 이후, 앞에서부터 하나씩 제거하며 x와 y초를 계산해주면 됩니다.
  • ex) 0110 -> 110 -> 10 -> 0

Big O(time)

• O(N)

Code

#define rep(i, a, b) for(int i = (a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i>(b); i--)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


string s;
int x, y;
int n, p, k;
int mn;
void input(){
    mn = 1000000001; // p = 100000이고 y 가 10000 인경우 max
    cin >> n >> p >> k >> s >> x >> y;
}
void solve(){
    input();
    p -= 1;
    rep(i, 0, k+1){
        int st = p + i;
        string tmp = "";
        int cur = st;
        int cnt0 = 0, cnt1 = 0;
        while(cur < n){
            if(s[cur] == '1') cnt1++;
            else cnt0++;
            tmp += s[cur];
            cur += k;
        }
        cur = 0;
        int cntDel = i;
        while(cur < (int)tmp.size()){
            int sum = cnt0 * x + y * cntDel;
            mn = min(mn, sum);
            cntDel += k;
            if(tmp[cur] == '0') cnt0--;
            cur += 1;
        }
    }
    cout << mn << '\n';
}
int main(){;
    //freopen("input.txt", "r", stdin);
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}