백준 14789번 Oversized Pancake Flipper - C++(cpp) 풀이

---

 

1. 한 자리에서 두 번 이상 뒤집을 필요가 없다.
2. 첫 팬케이크를 뒤집을 수 있는 방법은 가장 왼쪽의 K개를 뒤집는 것뿐이다.
3. 왼쪽부터 차례로 happy side가 되도록 뒤집는다.

 

1. 한 자리에서 두 번 이상 뒤집을 필요가 없다.

 한 자리에서 두 번 이상 뒤집을 필요가 없다. 짝수번 뒤집는 것은 안 뒤집는 것과 같고, 홀수번 뒤집는 것은 한 번 뒤집는 것과 같기 때문이다. 따라서 각 자리에서 뒤집을지 말지만 결정하면 된다.

 

2. 첫 팬케이크를 뒤집을 수 있는 방법은 가장 왼쪽의 K개를 뒤집는 것뿐이다.

 뒤집을 수 있는 자리는 총 N-K+1개이다. 이때 첫 번째 팬케이크를 뒤집을 수 있는 자리는 가장 왼쪽의 K개를 뒤집는 자리뿐이다.

 

3. 왼쪽부터 차례로 happy side가 되도록 뒤집는다.

 1,2번 사실을 통해 왼쪽부터 차례로 happy side로 만들어주는 그리디한 방법이 유효하다는 것을 알 수 있다. 첫 번째 팬케이크를 happy side로 만들고 나면, 더 이상 첫 번째 팬케이크는 뒤집을 일이 없고, 따라서 두 번째~마지막 팬케이크를 모두 happy side로 만들어야 하는, S[1...]을 입력으로 받은 상황이 된 것과 같다.

 

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

int flip_cnt[1001];

void flip(int s, int e) {
    for (int i=s; i<=e; i++) flip_cnt[i]++;
}

int solution(string s, int k) {
    int ret = 0;
    
    for (int i=0; i<s.size()-k+1; i++) {
        if (((s[i] == '-' ? 1 : 0) + flip_cnt[i]) % 2 == 0) continue;
        flip(i, i+k-1);
        ret++;
    }
    
    for (int i=s.size()-k+1; i<s.size(); i++) {
        if (((s[i] == '-' ? 1 : 0) + flip_cnt[i]) % 2 != 0) return -1;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    
    for (int t=1; t<=T; t++) {
        memset(flip_cnt, 0, sizeof(flip_cnt));
        
        string S;
        int K;
        cin >> S >> K;
        
        int ans = solution(S, K);
        
        cout << "Case #" << t << ": ";
        if (ans == -1) cout << "IMPOSSIBLE";
        else cout << ans;
        cout << "\n";
    }

    return 0;
}