Problem E 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1520/problem/E

문제 해결 방법은 각 위치마다 해당 위치를 기준으로 양들을 모았을 때의 이동 횟수를 구한 후,

비교하여 가장 적은 이동 횟수를 찾는 방법을 사용했다.


이동 횟수를 구하는 방법은 string을 왼쪽에서 오른쪽으로 한번, 오른쪽에서 왼쪽으로 한번 순회하여 구한다.

왼쪽에서 오른쪽으로 순회하면서 저장할 배열을 v1,

오른쪽에서 왼쪽으로 순회하면서 저장할 배열을 v2라고 하자.

순회하면서 계산하는 방법은 아래와 같다.


현재 위치를 기준으로 왼쪽 or 오른쪽에 있는 양들의 수를 shp,

현재 위치에 해당하는 index를 pos라고 한다면,

왼쪽에 있는 양들에 대해 계산하는 경우에 v1[0] = 0이다.

나머지 위치에 대해 다음과 같은 규칙으로 계산이 진행된다.

1. 현재 위치 pos에 양이 있다면 v1[pos] = v1[pos - 1], shp++

2. 현재 위치 pos가 비어있다면 v[pos] = ( v1[pos - 1] + shp )


오른쪽에서 왼쪽으로 순회하며 계산하는 경우도 방법은 위와 같다.

v2[n - 1] = 0이고 나머지 위치에 대해 계산한다.


v1과 v2를 구한 후에 0 ~ n - 1 위치를 모두 순회하여 총 이동 횟수가 가장 적은 값이 답이다.

0번째 위치는 결국 오른쪽에 있는 양들만 모두 이동한 것이므로 v2[0]이 되고,

n - 1번째 위치도 마찬가지로 v1[n - 1]이 된다.

나머지 위치는 v1[pos] + v2[pos + 1]로 계산한다.

( pos까지 왼쪽 양들이 이동했으면 오른쪽 양들은 pos에 겹치지 않게 pos + 1 자리까지 이동해야 정렬되므로. )


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        int n;
        cin >> n;
 
        string str;
        cin >> str;
 
        vector<long long> left(n), right(n);
        left[0] = 0;
        right[n - 1] = 0;
 
        int sheep = 0;
 
        if (str[0] == '*')
            sheep = 1;
 
        for (int i = 1; i < str.length(); i++) {
            if (str[i] == '*') {
                sheep++;
                left[i] = left[i - 1];
            }
            else
                left[i] = left[i - 1] + sheep;
        }
 
        if (str[n - 1] == '*')
            sheep = 1;
        else
            sheep = 0;
 
        for (int i = str.length() - 2; i >= 0; i--) {
            if (str[i] == '*') {
                sheep++;
                right[i] = right[i + 1];
            }
            else
                right[i] = right[i + 1] + sheep;
        }
        
        long long ans = (left[n - 1] > right[0]) ? right[0] : left[n - 1];
 
        for (int i = 0; i < n - 1; i++) {
            if (ans > left[i] + right[i + 1])
                ans = left[i] + right[i + 1];
        }
 
        cout << ans << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기