수열의 장인

작성일 | In

[백준] 10885번 - 수열의 장인

문제 링크

ucpc 2015 예선 문제.
n의 크기가 최대 100,000 이라 O(nlogn) 혹은 O(n) 의 시간복잡도를 갖는 해결 방법이 필요한 문제이다.

문제 풀이에 어려움을 느껴 wasd222님의 포스트을 참고했다.

수열에 등장하는 수가 -2 이상 2 이하의 정수이므로 2 혹은 -2의 개수에 따라 답이 정해진다.

2 혹은 -2가 없다면 답은 0 혹은 1이 된다. n이 2 이상이므로 -1은 어떤 수열이 주어지던 정답이 될 수 없다.

2 혹은 -2가 수열에 없다면 수열 원소들 중 최대 원소가 답이 되므로, 처음에 수열을 입력받을 때 최대 원소를 ans에 기록해둔다.

알고리즘은 Greedy하게 진행된다. 주어진 수열을 좌->우, 우->좌 이렇게 2번 선형 탐색한다. 탐색할 때 2 혹은 -2의 개수(nowTwo), 음수의 개수(nowMinus) 를 카운트한다. 음수의 개수가 짝수일 때마다 수열 내 연속으로 등장하는 2 혹은 -2의 최대 개수를 갱신한다. 이 때, 수열 원소 최대값이 0이 아니라면 정답은 확실하게 1 이상이므로 ans값을 1로 만들어준다.
탐색을 끝낸 뒤에는 수열에서 연속으로 등장한 2 혹은 -2의 최대 개수(ansTwo) 만큼 ans에 곱해주고, 정답을 출력한다.

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
63
64
65
#include <bits/stdc++.h>
using namespace std;

#define MAX 1000000007

int seq[100000];
long long ans;
int ansTwo;

// 현재 수열 원소값에 따라 nowTwo, nowMinus, ansTwo, ans를 갱신한다.
void check(int idx, int& nowTwo, int& nowMinus) {
    // 현재 원소가 0이면 nowTwo, nowMinus를 0부터 다시 세야한다.
    // 또한, 수열이 0 0 0 ... 과 같이 전부 0인 경우,
    // 마지막 if문에서 ans = 1이 수행되면 안되므로 바로 리턴해준다.
    if(seq[idx] == 0) { 
        nowTwo=0; nowMinus=0; 
        return; 
    }
    else if(seq[idx] < 0) {
        ++nowMinus;
        if(seq[idx] == -2) ++nowTwo;
    }
    else if(seq[idx] == 2) ++nowTwo;

    // 현재까지의 수열 탐색에서 2 혹은 -2 개수가 짝수면 ansTwo를 갱신하고,
    // 마지막에 ans에 2를 누적으로 곱하기 위해 ans를 1로 초기화한다.
    if(nowMinus % 2 == 0) {
        ansTwo = ansTwo < nowTwo ? nowTwo : ansTwo;
        ans = 1;
    }
}

int main(void) {
    int t;
    scanf("%d", &t);

    while(t--) {
        int n;
        scanf("%d", &n);

        ans = -3; ansTwo = 0;
        for(int i=0; i<n; ++i) {
            scanf("%d", &seq[i]);
            ans = ans < seq[i] ? seq[i] : ans;
        }

        // 왼 -> 오 선형탐색
        int nowTwo=0, nowMinus=0;
        for(int i=0; i<n; ++i)
            check(i, nowTwo, nowMinus);
        
        // 오 -> 왼 선형탐색        
        nowTwo=0; nowMinus=0;
        for(int i=n-1; i>=0; --i)
            check(i, nowTwo, nowMinus);

        // 2 누적 곱셈
        // ansTwo가 0이면 자연스레 수행되지 않으므로 
        // 수열에 0 혹은 1밖에 없는 경우도 정확한 정답을 출력할 수 있다.
        while(ansTwo--)
            ans = (ans << 1) % MAX;

        printf("%lld\n", ans);
    }    
}
0%