극좌 극우로 부터 시작해서, 높이가 낮은 사이드를 당기면서 최대값을 갱신하면 된다.

 

낮은 쪽을 당기는 이유는, 낮은 쪽 사이드가 정답일 경우가 없기 때문.(현재 최대값이 정답인 경우를 제외하고)

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        ret = 0
        
        while(left < right):
            ret = max(ret, (right - left) * min(height[right], height[left]))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        return ret

https://www.acmicpc.net/problem/15673


수열에서 연속 부분 수열 두개를 골라 그 곱이 가장 클 때 얼마나 클지 알아내야 한다.


연속 부분 수열이 얼마나 클지를 알아내는 방법은 디피 문제를 풀 때 쉽게 접할 수 있는 문제다.


dp[x]를 x번째 인자를 포함한 부분 수열 중 합이 가장 큰 수를 저장하게 정의해 놓으면,


dp[x]는 dp[x-1]이 음수인 경우와 양수인 경우로 나눠 원타임에 값이 정해진다.



또한 새로운 디피 배열 lmax를 정의할 수 있게 되는데,


이번엔 lmax[x]는 x번째 인자를 반드시 포함하지 않아도, x까지 수열의 부분 수열 중 합이 가장 큰 수를 저장한다고 정의해 놓으면,


lmax[x] = max(lmax[x-1], dp[x])로 원타임에 값이 정해진다.


즉 x가 포함되던지 안되던지 두 케이스 중 큰 값으로 정해지는 것이다.



이를 응용해서 왼쪽에서 부터, 오른쪽에서 부터, 최대합 부분수열, 최소합 부분수열을 모두 n타임에 구할 수 있다.


그러고 난 다음 부분 수열 두 개로 나눌 기준점을 n개 중에 골라서 비교하는 작업도 n타임에 수행할 수 있다.


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
66
67
68
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int n;
ll arr[100001];
 
ll dmin[100001], dmax[100001];
ll lmin[100001], lmax[100001];
ll rmin[100001], rmax[100001];
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
 
    lmin[1= lmax[1= dmin[1= dmax[1= arr[1];
 
    for (int i = 2; i <= n; ++i) {
        if (dmax[i - 1< 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i - 1+ arr[i];
 
        if (dmin[i - 1> 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i - 1+ arr[i];
 
        lmin[i] = min(lmin[i - 1], dmin[i]);
        lmax[i] = max(lmax[i - 1], dmax[i]);
    }
 
    memset(dmin, 0sizeof(dmin));
    memset(dmax, 0sizeof(dmax));
 
    rmin[n] = rmax[n] = dmin[n] = dmax[n] = arr[n];
 
    for (int i = n - 1; i >= 1--i) {
        if (dmax[i + 1< 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i + 1+ arr[i];
 
        if (dmin[i + 1> 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i + 1+ arr[i];
 
        rmin[i] = min(rmin[i + 1], dmin[i]);
        rmax[i] = max(rmax[i + 1], dmax[i]);
    }
 
    ll ans = LLONG_MIN;
    for (int i = 1; i < n; ++i) {
        ans = max(ans, lmin[i] * rmin[i + 1]);
        ans = max(ans, lmin[i] * rmax[i + 1]);
        ans = max(ans, lmax[i] * rmin[i + 1]);
        ans = max(ans, lmax[i] * rmax[i + 1]);
    }
 
    cout << ans;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

https://www.acmicpc.net/problem/15668


0 ~ 9 까지 숫자 카드 스티커들을 한 번씩만 사용해 n = a + b 의 a와 b를 만들어야 한다.



여러 풀이 중에 내 생각에 제일 기똥찬 풀이는,


a와 b중에 작은 수를 b라고 하면, b의 가능 범위가 작아지므로, 완탐으로 때릴 수 있다는 것이다.



b에 스티커 5장을 쓰면 a도 5장이 되므로 b엔 최대 5장까지만 쓸 수 있다.


또한 b의 맨 앞자리는 끽 해야 8이므로, 1~87654가 b의 가능범위이다.


b가 정해지면 a도 정해지므로, 구만번 만에 풀리는 문제.



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
#include <bits/stdc++.h>
using namespace std;
 
int n;
 
bool func(int x, int& st) {
    while (x) {
        int tmp = (1 << (x % 10));
        if (st & tmp)
            return false;
 
        st |= tmp;
        x /= 10;
    }
 
    return true;
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= 87654 && i < n; ++i) {
        int used = 0;
 
        if (!func(i, used))
            continue;
        if (!func(n - i, used))
            continue;
 
        cout << n - i << " + " << i;
        return 0;
    }
 
    cout << -1;
}
cs


https://www.acmicpc.net/problem/16116


구현이지만 논리력에 따라 // 관찰력에 따라 코드가 짧아질 수 있는 문제



다음을 관찰하면 코드가 짧아진다.



한 큐브가 [a b c] 였다면, 반드시 나머지 일곱 개 중에 윗 그림과 같은 세 개의 큐브가 존재해야 한다.


헌데 큐브는 요리 조리 돌려도 똑같기 때문에


한 큐브 마다 -> 세 가지 방향으로 -> 나머지 7가지 큐브 중에 -> 두면이 맞닿고 같은 큐브가 존재(중요) -> 그것도 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
#include <stdio.h>
 
char str[6];
char cb[8][4];
 
int main() {
    for (int i = 0; i < 8++i) {
        fgets(str, sizeof(str), stdin);
        cb[i][0= str[0];
        cb[i][1= str[2];
        cb[i][2= str[4];
        fgets(str, sizeof(str), stdin);
    }
 
    bool cannot = false;
    for (int i = 0; i < 8++i) {
        for (int j = 0; j < 3++j) {
            int left = cb[i][j];
            int top = cb[i][(j + 1) % 3];
            int cnt = 0;
 
            for (int k = 0; k < 8++k) {
                if (i != k) {
                    for (int l = 0; l < 3++l) {
                        if (cb[k][l] == left && cb[k][(l + 2) % 3== top) {
                            cnt++;
                        }
                    }
                }
            }
 
            if (cnt != 1)
                cannot = true;
        }
    }
 
    if (cannot)
        puts("NO");
    else
        puts("YES");
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 15668 방 번호  (0) 2018.10.02
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

다들 다익스트라를 배우고 이해는 한다.


아~ 계속 간선 길이를 늘려가면서 점마다 우선순위큐로 dp를 찍어주면 되는구나~


이해는 하고 기초 문제를 풀고 나면 다익스트라를 다 아는 것 같은 착각이 든다 ㅎㅎ



근데 이제 다익스트라를 조금만 꽈서 낸 문제면 풀질 못한다 ㅜㅜ


어느 알고리즘이나 응용이 어렵지만, 내가 느끼기엔 다익스트라가 유독 까다롭더라.


그래서 이제부터 좀 다양한 다익스트라 문제들을 올리려고 한다.


이 글을 호오오오옥시 읽는 분들도 아는 문제가 있으면 추천을 부탁드립니다.


---------------------------------------------------------------------------------------------------------------------------------------------------------------------



1) 백준 16118 달빛 여우


https://www.acmicpc.net/problem/16118


조금만 꽈서 낸 문젠데 세 번이나 틀리고 맞았다 ^^


여우의 경우 1번 정점부터 나머지 정점까지 최소경로의 길이는 순수 다익스트라로 구할 수 있다.


늑대의 경우 내가 현재 정점에 오기전에 2배 빠르게 왔는지, 느리게 왔는지 기억해야 한다.


그래서 나는 구현을 쉽게 할려고(정말?), 간선을 2배로 뿔렸다. 즉 2배 빨라지는 길, 2배 느려지는 길을 추가했다.


그러면 전에 빨라지는 길로 왔었다면, 이번엔 느려지는 길로만 갈 수 있게 된다.


dp(fox, wolf)에는 빠르게 왔는지, 느리게 왔는지를 둘 다 기록했다.


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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long ll;
 
int n, m;
int a, b;
ll fox[4001], wolf[4001][2], c;
 
struct edge_f {
    int to;
    ll cost;
 
    bool operator< (const edge_f& e) const {
        return cost > e.cost;
    }
};
 
struct edge_w {
    int to;
    ll cost;
    bool fast; //길 종류
 
    bool operator< (const edge_w& e) const {
        return cost > e.cost;
    }
};
 
int main() {
    scanf("%d %d"&n, &m);
 
    vector<vector<edge_f>> vf(n + 1);
    vector<vector<edge_w>> vw(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %lld"&a, &b, &c);
        vf[a].push_back({ b, 2ll * c });
        vf[b].push_back({ a, 2ll * c });
 
        vw[a].push_back({ b, c, false });
        vw[a].push_back({ b, 4ll * c, true });
        vw[b].push_back({ a, c, false });
        vw[b].push_back({ a, 4ll *c, true });
    }
 
    //////////////////////여우
    memset(fox, -1sizeof(fox));
 
    priority_queue<edge_f> pqf;
    pqf.push({ 1, 0ll });
 
    while (!pqf.empty()) {
        edge_f e = pqf.top(); pqf.pop();
 
        if (fox[e.to] != -1) {
            continue;
        }
 
        fox[e.to] = e.cost;
 
        for (auto next : vf[e.to]) {
            if (fox[next.to] != -1) {
                continue;
            }
            pqf.push({ next.to, e.cost + next.cost });
        }
    }
    //////////////////////여우
 
    //////////////////////늑대
    memset(wolf, -1sizeof(wolf));
 
    priority_queue<edge_w> pqw;
    pqw.push({ 1, 0ll, true });
 
    while (!pqw.empty()) {
        edge_w e = pqw.top(); pqw.pop();
 
        if (wolf[e.to][e.fast] != -1)
            continue;
 
        wolf[e.to][e.fast] = e.cost;
 
        for (auto next : vw[e.to]) {
            if (wolf[next.to][next.fast] != -1)
                continue;
            
            if (e.fast != next.fast) { //종류가 다른 길로 가야 해
                pqw.push({ next.to, e.cost + next.cost, next.fast });
            }
        }
    }
    //////////////////////늑대
 
    int ans = 0;
    ll _min, _max;
    for (int i = 1; i <= n; ++i) {
        _min = min(wolf[i][0], wolf[i][1]);
        _max = max(wolf[i][0], wolf[i][1]);
 
        if (_min == -1) { //못 가는 노드가 있을 경우
            if (fox[i] < _max) {
                ans++;
            }
        }
        else {
            if (fox[i] < _min) {
                ans++;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


2) bitonic path


scpc 2차 예선 문제였는데 링크를 찾고 있습니다 ㅜ

'알고리즘 > Dijsktra 다익스트라' 카테고리의 다른 글

백준) 1753 최단경로  (0) 2017.09.09
다익스트라 도입  (0) 2017.07.11

https://www.acmicpc.net/problem/15957


1. 트리


트리의 루트에 쿼리가 가해지면 자식들의 점수가 모두 더해진다.


-> 트리를 dfs 돌면서 번호를 매기면, 루트 노드 부터 자식들이 연속해서 들어있는 배열을 만들 수 있다. = 트리 순회 배열이라고 한단다.



2. 쿼리


트리 순회 배열에 쿼리가 가해진다.


이제 쿼리는 배열의 일부 구간을 증가시키는 쿼리가 된다.


-> 일부 구간을 빠르게 증가시키는 방법이 필요하다.


-> 증가시켰으면 값이 얼마인지도 빠르게 알아낼 방법이 필요하다. = 펜윅트리의 ( range update & point query ) 모드를 사용하자.



3. 펜윅 트리


이 자료구조는 다음 두 기능을 로그시간에 제공하는 자료구조다.


1) update(p, v) : p번째 원소를 v만큼 증가시킨다.


2) query(p) : 첫번째 원소부터 p번째 원소까지의 합을 알려준다.


즉 point update & range query를 로그시간에 수행한다.


이를 조금만 응용하면 range update & point query 모드로 바꿀 수 있다.



원래 배열을 a라고 하고, 배열 b[x] = a[x] - a[x - 1] 이라고 정의해보자.


그러면 이제 a의 입장에서, a[x]는 b[x] + b[x - 1] + ... 즉 누적합이 된다.


이제 두 기능을 b에 대고 수행한다고 생각해보자.


1) update(p, v)


-> 예를 들어 update(3, v)라면, a[1]과 a[2]는 가만히 있고, a[3]부터 v씩 늘어난 것이다. 왜냐하면 b의 정의 때문에.


따라서 [from, to] 구간을 v만큼 증가시키고 싶다면, update(from, v) 와 update(to + 1, v) 두 번으로 배열 a를 다 조질수 있다.


2) query(p)


-> b[1] + b[2] + ... + b[p] = a[p] 이니까, a의 p번째 원소 값을 구하는 쿼리로 변경되었다.



이처럼 펜윅트리는


1) point update & range query


2) range update & point query


3) range update & range query


총 3가지 모드를 제공한다. 3번째 모드는 차후에 설명하는 것으로.. ㅎㅎ




이제 트리에 가해지는 쿼리를, 펜윅트리에서 로그시간에 수행할 수 있게 되었다.


하지만


1) 모든 쿼리를 수행해보면서 매번 모든 가수가 평균 점수를 넘는지 확인


2) 모든 가수마다 쿼릐를 수행해보면서 언제 평균 점수를 넘는지 확인


어떤 방법으로도 N * K * log(N)으로 시간이 오바된다.



4. 시간 줄이기


포인트는 가수들의 평균점수는 쿼리들이 수행되는 동안 절대 내려가지 않는다는 점이다.


따라서 단조증가하고, 이는 이분 탐색을 떠올리게 해준다.


하지만 가수마다 이분 탐색으로 조지는 것 보다, 모든 가수들의 구간을 줄여나가는 방법이 있단다. -> 병렬 이분 탐색



이 알고리즘의 구조를 보면, 가수마다 구간이 있고 구간의 중앙값은 타겟이 된다.


이제 쿼리를 순차적으로 수행할 텐데, 현재 수행하는 쿼리가 타겟과 같다면 그 가수는 구간을 반으로 줄일 수 있다.


쿼리를 전부 수행하고 나서, 구간이 변화한 가수가 있다면, 다시 처음부터 쿼리를 수행하는 짓을 반복한다.


말로는 머가 개선된건지 모르겠지만, 나중에 코드로 보면 더 빠르겠구나 할 꺼다.




'알고리즘 > 미분류' 카테고리의 다른 글

백준) 15668 방 번호  (0) 2018.10.02
백준) 16116 작은 큐브러버  (0) 2018.10.01
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

A를 6분에 풀고


B에서 너무 시간을 오래 잡아먹었다.


관찰결과, (x,y)에서 |x|==|y| 이거나 절대값 차이가 홀수냐 짝수냐에 따라 다 다르길래 마음만 급해서 구현실수하구....


C에서 너무 수학적으로 생각하느라 또 시간 소비.


D는 그나마 빨리 풀었다. 그리디하게 생각한게 적중.


다시 C로 돌아와서 허어ㅓㅓㅓㅓㅓ 하다가 끝나버렸다.




문제의 C문제는 


0이 아닌 자릿수가 3개 이하인 자연수 = Classy number 가 [L, R] 구간에 몇 개나 있는지 세는 문제였다.


조합으로 수식 세우고 구현하면 되기도 하지만, 나처럼 구현상의 실수를 할 수 있다.


그래서 미리 Classy number를 다 구해놓고, (10^18 이하에서) 이분탐색으로 구간 상의 개수를 세면 되는 문제였다고 한다. ㅎㅎ


솔직히 이런 유형의 문제를 처음봤다. 미리 다 구해노코 빠박하는게 좀 더 컴퓨터적인 사고인거 같은데,


수학적으로만 접근 한걸 보면 백준만 허구헌날 해서 그런가 싶기도 하고...



'알고리즘 > 미분류' 카테고리의 다른 글

백준) 16116 작은 큐브러버  (0) 2018.10.01
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19
백준) 11003 최소값 찾기  (0) 2018.07.13

다음에 길게 길게 설명하기로 하고,


문제 풀면서 느낌 감상만 먼저 옮기려고 합니당.



학교 수업시간에 배운 두번의 DFS로 SCC들을 구하는 방법과,


한 번의 dfs로 SCC들을 구하는 방법을 비교해 봤는데, 확실히 후자의 방법이 두 배 정도 더 빨랐다.


두 번의 dfs는 간단해서 짜는데 빠르게 짤 수 있는 반면, 한 번의 dfs는 이해한지 얼마 안돼서 그런가 코드가 길긴하다.



간단히 설명하면,


전자의 방법은 먼저 dfs를 돌긴하는데 finish되는 순으로 stack에 push 해두었다가,


pop하면서 역간선 그래프에 대해 dfs를 다시 돌면서 scc로 묶는 방법이다. (a->b로 갈 수 있으면, b->a로도 갈 수 있어야 한다.)



후자의 방법은 dfs 트리를 활용하는데, 방문하는 순서대로 노드들에게 번호를 매기면서 stack에 push하고, 지금의 dfs가 어떤 노드로부터 


시작되었는지를 활용하여 scc로 묶는 방법이다. 후자는 확실히 코드를 봐야 이해가 빠르다.



Strongly Connected Component


https://www.acmicpc.net/problem/2150


1. 2150 은 기본 문제로 scc들을 구하는 문제였다.



도미노


https://www.acmicpc.net/problem/4196


2. 4196은 scc를 구한 다음에 더 풀어야 되는 문제였다.


scc내에선 하나만 무너지면 다른 노드들도 다 넘어진다. 따라서 그래프를 scc들 끼리의 그래프로 재편집한다음에,


scc들의 indegree를 계산하고, indegree가 0인 scc들의 갯수를 세면 풀 수 있다.



ATM


https://www.acmicpc.net/problem/4013


3. 4013은 scc를 구하고 indegree를 구하고 더 풀어야 되는 문제였다.


scc를 구할 때 각 scc들의 value 합을 구해놓고 scc들 끼리의 그래프로 재편집해야 한다.


이후 indegree를 계산한 다음에, 위상정렬로 출발점이 속한 scc에서 레스토랑이 있는 scc까지의 최대 value 합을 각각 구하면 된다.

https://www.acmicpc.net/problem/2512



예산



아 parametric search 구나


라고는 빨리 알았지만, 이분탐색의 늪에 빠졌다가 뭔가 깨달음을 얻어서 여기에 옮기고자 한다.




k번째 숫자(https://www.acmicpc.net/problem/7469)를 parametric search로 풀고, 이 문제도 parametric search로 풀었다.


전자는


1
2
3
4
5
6
7
8
9
10
int l = -1000000000;
int r = 1000000000;
 
while (l < r) {
    int mid = (l + r) >> 1;
    if (q(10, n - 1, i - 1, j - 1, mid) >= k)
        r = mid;
    else
        l = mid + 1;
}
cs

후자

후자는


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (l < r) {
    int mid = (l + r + 1/ 2;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] >= mid)
            sum += mid;
        else
            sum += arr[i];
    }
 
    if (sum <= m)
        l = mid;
    else
        r = mid - 1;
}
cs



와 같다.




전자의 경우 mid가 성공했다면, 그 값을 포함한채 오른쪽을 좁혀야 하고,


(k번째 숫자를 찾아야 하므로, 더 큰 값은 의미가 없고, mid는 정답일 수 있으므로 버리면 안된다.)


후자의 경우 mid가 성공했으면, 그 값을 포함한채 왼쪽을 좁혀야 한다.


(최대 예산액을 찾아야 하므로, 작은 값은 의미가 없으며, mid는 정답일 수 있으므로 버리면 안된다.)



따라서 left와 right로 mid를 정하는 기준이 달라지는데, 이유를 말로 하긴 복잡하니까 그림으로 설명해보겠다.



mid 를 (left + right) / 2 로 하느냐, (left + right + 1) / 2로 하느냐의 차이점은, (성공했을 때 좌우를 변경하는 로직이 완벽했을 때)


결국엔 range가 2일 때 선명하게 드러나는데,


이번 예산 문제의 경우 mid 를 (left + right) / 2 로 하고 성공했을 경우, 


위 그림과 같이 무한루프에 빠지게 된다. 



반대로 k번째 숫자 문제는,


mid 를 (left + right + 1) / 2 로 한다면 성공했을 경우 무한루프에 빠지게 된다.



따라서 좌우를 버리는 로직을 완벽히 세워놨다면, 모든 parametric search를 위 두 케이스 중에 알맞은 케이스로 풀면 된다


라는게 내린 결론인데, 평소 while(left <= right)인 코드를 많이 봐왔던지라 차이점이 궁금해지긴 한다.


정파말고 사파식 공부를 하는 중이라 깊이가 모자른걸 요새 크게 통감하고 있다 ㅎㅎ;


풀 코드는 다음과 같다.


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, m;
int arr[10000];
 
int main() {
    int l = 1, r = 0;
 
    scanf("%d"&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d"&arr[i]);
        r = max(r, arr[i]);
    }
    scanf("%d"&m);
 
    while (l < r) {
        int mid = (l + r + 1/ 2;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (arr[i] >= mid)
                sum += mid;
            else
                sum += arr[i];
        }
 
        if (sum <= m)
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d", l);
}
cs


https://www.acmicpc.net/problem/11003



정수 배열에 대해, 각 인덱스로 자신이 부분수열의 끝이고 길이가 L인 부분수열을 만들 수 있다.


각 부분수열의 최소값을 구해야 한다. (정수 배열의 길이 <= 오백만)



처음엔 세그먼트 트리 풀이만 생각이 났다. 근데 오백만이라 nlogn만 해도 오억이라 시간안에 풀 수 없었다.


복잡한 세그먼트 트리로만 헤매고 있었던 이유는,



각 부분수열의 최소값을 구할 때, 전 인덱스로 구한 최소값을 활용하는게 어려웠기 때문이다.


최소값이 부분수열의 맨 처음에 있었다면, 이번에 최소값을 구할 땐, 이전의 최소값은 구간에 포함이 안되고 새로 구해야 했다.


이러한 최악의 경우는 계속 일어날 수 있고(오름차순 정렬된 배열이라면), 좋은 풀이가 아니었다.



결국 이렇게 최악의 경우에서, 다음으로 작은 최소값을 알고 있으면 해결할 수 있다.


이 최소값도 다시 구간에서 벗어날 수 있으므로, 최소값들 후보를 죄다 갖고 있으면 된다!



이러한 자료구조를 고민하다가 덱을 쓰기로 했다.


덱의 맨 앞은 최소값을 가지고, 뒤로 갈수록 다음 최소값 후보들이 이어진다.



따라서 덱의 front에선 최소값들을 활용하고, 뒤로는 최소값 후보들을 집어넣으면 된다.


작업후에는 L-i ~ i 까지 최소값들 후보들이 덱에 들어가 있을 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
 
int n, l, a;
deque<pair<intint>> dq;
 
int main() {
    scanf("%d %d"&n, &l);
    for (int i = 0; i < n; ++i) {
        while (dq.size() && dq.front().second <= i - l)
            dq.pop_front();
 
        scanf("%d"&a);
        while (dq.size() && dq.back().first >= a)
            dq.pop_back();
 
        dq.push_back({ a,i });
        printf("%d ", dq.front().first);
    }
    return 0;
}
cs


+ Recent posts