3144 자석

어려웠다...!

문제 이해는 했는데 이걸 그래서 어떻게...? 싶은 문제였다. 

 

내가 이해한 내용

- 처음에 자석이 같은 방향이면 전부 합쳐짐

- 합쳐진 자석을 바탕으로 길이를 L로 맞추면 된다

- 중간에 있는 자석 뒤집으면 무조건 3개가 합쳐짐

- 양 끝에 있는 자석 뒤집으면 이건 2개면 합쳐짐

 

어... 이제... 어... 어떻게... 합치죠...?

 

그래서 역시나 북님의 도움

1. 배열에 부분합을 저장한다 sum[i] = 0...i번째 합

2. 만약 sum[i]가 X이고 sum[j]가 X - L이면, sum[i] - sum[j]는 L이다. 이런 i, j를 찾으면 됨!!

3. 그럼 반대로 pos(L) 이런 식으로 저장하자. sum[i] = L, pos(L) = i 이렇게 합을 기준으로 인덱스를 저장

 

그런데 우리는 횟수가 가장 작은 걸 출력하고 싶다. 

i - pos(X - L)이 가장 큰 걸 찾자 (이거 이해 못함 왜지)

홀수 인덱스 / 짝수 인덱스 나눠서 생각하는데

i가 홀수인 경우에는 pos(X-L)이 짝수인 걸 찾고

짝수인 경우에는 홀수인 걸 찾는다.. 헝... 뭔가 이러면 무조건 홀수인 경우만 찾는 게 아닌가?? 양 끝에 짝수인 경우는 ...??

 

암튼 이까지 내가 이해를 못한 건

i - j가 가장 큰게 횟수가 작은게 맞는지?

인덱스 차가 홀수이게 하는데 이러면 모든 경우를 커버할 수 있는지?? 

이 두가지 이다. 

 

이해를 못한게 남아있어도 괜찮다. 나한테는 코드가 있다. 원래 컴공은 코드로 말한다. 

 

----

코드 조각조각 땃땃따 분석하기

    int n, l;
    scanf("%d %d", &n, &l);
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "NS")
            arr[i] = 1;
    }

입력받는 부분

NS이면 1, SN이면 0을 arr에 저장한다. 아...! 별거 아니긴 한데 기본적으로 0으로 초기화 되니깐 0은 저장 안 해도 되는군

 

    vector<int> p;
    int len = 1;
    int now = arr[0];
    for (int i = 1; i < n; i++) {
        if (now != arr[i]) {
            p.push_back(len);
            len = 1;
            now = arr[i];
        }
        else
            len++;
    }
    p.push_back(len);

000 11111 이렇게 같은 숫자끼리 이어진 길이를 p에 저장한다

 

15 13

SN NS NS SN NS SN SN NS NS SN SN NS NS NS SN

 

이 예시를 들고오면

011010011001110이니깐

1 2 1 1 2 2 2 3 0이 저장된다

 

int ans = 987654321;
    
    int s = 0;
    for (int i = 0; i < p.size() && s < l; i++) {
        s += p[i];
        if (s == l)
            ans = (i + 1) / 2;
    }
    
    s = 0;
    for (int i = (int)p.size() - 1; i >= 0 && s < l; i--) {
        s += p[i];
        if (s == l)
            ans = min(ans, ((int)p.size() - i) / 2);
    }

이제 왼쪽부터 돌면서 합이 l이 되는 걸 찾는다. 합이 l이라면 ans를 저장하는데 이게 무슨 의미지..? 물어봐야겠다

아 게다가 이러면 무조건 0부터 시작하는 합만 구하는 거 아닌가??

 

다음으로 오른쪽부터 돌면서 합이 l이 되는 걸 찾는다. 음 마찬가지로 모르겠다. 

 

    map<int, int> pos[2];
    pos[1][0] = -1;
    
    s = 0;
    for (int i = 0; i < p.size(); i++) {
        s += p[i];
        if (pos[(i + 1) % 2].find(s - l) != pos[(i + 1) % 2].end())
            ans = min(ans, (i - pos[(i + 1) % 2][s - l]) / 2);
        
        pos[i % 2][s] = i;
    }
    
    printf("%d\n", ans);

다시 0번째 인덱스부터 p[i]값을 합친다

헉

i + 1 값을 확인하는데 어...? s - l을 찾는다...? 

어..