중복값 처리와 배열 초기화 때문에 굉장히 애먹은 문제이다....

접근한 방식은 입력받은 하나의 수열값들을 인덱싱을 통해 표시를 해주고(음수값 + 고정 Value처리)

나머지 하나의 수열을 입력받으면서

교차점일 경우에 해당 인덱스 지점까지의 Prefix_Sum값을 비교해주는 것이다. 
(before 교차점까지의 PrefixSum의 차이값 비교)

하지만... 인덱싱 처리해준 값들을 여러테케를 돌리는 문제이다보니 

초기화 해주지 않은 것이 화근이었다...ㅠ

좀더 꼼꼼할 필요가 있는 자신을 돌아보게됨..

스티커 이미지

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

<Code>

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
//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
 
#define N_ 10001
#define sz(x) x.size()
using namespace std;
 
typedef long long ll; 
typedef double db; 
int a[N_], a1[N_], Prefix[N_], Prefix1[N_], n, m, Num[20002], Sum1, Sum2, ans, before, before1;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while (cin >> n && n > 0) {
        ans = 0;  before = 0; before1 = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i]; Num[a[i] + 10000] = i;
            Prefix[i] = a[i];
            Prefix[i] += Prefix[i - 1];
        }
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> a1[i];
            Prefix1[i] = a1[i];
            Prefix1[i] += Prefix1[i - 1];
            if (Num[a1[i] + 10000]) {
                int lower_Sum = Num[a1[i] + 10000];
                Sum1 = Prefix[lower_Sum] - Prefix[before];
                Sum2 = Prefix1[i] - Prefix1[before1];
                before1 = i; before = lower_Sum;
                ans += (Sum1 > Sum2) ? Sum1 : Sum2;
            }
        }
        int r = Prefix[n] - Prefix[before];
        int q = Prefix1[m] - Prefix1[before1];
        ans += (r > q) ? r : q;
        cout << ans << '\n';
        for (int i = 0; i <= 20000; i++)
            Num[i] = 0; 
    }
    return 0;
}


저작자표시

'PS) BOJ > Binary Search' 카테고리의 다른 글

[C++] 랜선 자르기 [BOJ 1654]  (0) 2018.08.16
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16
[C++]입국심사[백준 3079]  (0) 2018.08.15

문제를 살펴보면 딱히 어려운 문제는 아니다. 

그냥 다익스트라 2차원으로 돌리면된다. 

흰색이 1 검은색이 0이라는 점에 착안하면 검은색에 가중치를 두기 위해 필자는 원본을 toggle 해줬다. 

그냥 벡터도 필요없이 dst 2차원을 갱신해주며 다익스트라를 돌려주자
(요즘 너무 쉬운것만 올리는것 같다 - 맨날 이소리하고 맨날 쉬운거 올린다)

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

2665번: 미로만들기
2665번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 미로만들기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 2961 1257 858 42.644% 문제 n×n 바둑판 모양으로 총 n 2 개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어가 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으
www.acmicpc.net

<Code>

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
// pda_pro12
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
 
#define INT 0x7fffffff
#define N_ 51
 
using namespace std;
 
int n, a[N_][N_], dst[N_][N_], dx[] = { -1,1,0,0 }, dy[] = { 0,0,1,-1 };
priority_queue<pair<pair<int, int>, int>> pq;
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%1d", &a[i][j]);
            a[i][j] = (a[i][j] == 0) ? 1 : 0; 
            dst[i][j] = INT;
        }
    }
    dst[0][0] = 0;
    pq.push({ {0,0},0 });
    while (!pq.empty()) {
        int v_x = pq.top().first.first; int v_y = pq.top().first.second;
        int dis = -pq.top().second;
 
        pq.pop();
        if (dis > dst[v_x][v_y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = v_x + dx[i]; int ny = v_y + dy[i]; 
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
            int n_dis = dis + a[nx][ny]; 
            if (n_dis < dst[nx][ny]) {
                dst[nx][ny] = n_dis; 
                pq.push({ {nx, ny}, -n_dis });
            }
        }
    }
    cout << dst[n - 1][n - 1]; 
    return 0;
}


저작자표시

'PS) BOJ > Disjoint_set' 카테고리의 다른 글

[C++] 네트워크 연결 [백준 3780]  (0) 2018.08.17
[C++] 공항 [BOJ 10775]  (0) 2018.08.17

전형적인 세그먼트 트리 문제인데 함정은 쿼리에 무조건 작은수~큰수라는 조건이 없으므로 
조건으로 잘 처리해주면 금방 풀수 있는 문제이다. 
바텀업 세그먼트 트리를 구현해서 풀었다. 

구간합 구하기 문제는 역시 세그먼트 트리 구현해서 푸는게 짱인거같다...
(내가 아는선에서는... ㅎ)

시간복잡도는 M*NlogN 만큼 소요되는것같다. 
주어지는 쿼리의 수가 10만턴정도이니 입출력을 줄여주는것도 시간을 충분히 줄여준다. 

참고로 덧셈과정에서 정수형을 넘어갈수 있으니 long long을 사용했다.


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

1275번: 커피숍2
1275번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 커피숍2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2852 596 419 19.886% 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은
www.acmicpc.net

<CODE>


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
//pda_pro12
#include<algorithm>
#include<iostream>
 
#define N_ 100000
#define INT 0x7fff0000
 
using namespace std; 
 
typedef long long ll;
ll a[N_], seg[N_ * 4], n, q; 
 
void init(int node, int x, int y) {
    if (x == y) {
        seg[node] = a[x]; 
        return; 
    }
    int mid = (x + y) >> 1; 
    init(node << 1, x, mid); 
    init((node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1];
    return; 
}
 
void update(int pos, int val, int node, int x, int y) {
    if (pos < x || pos > y) return; 
    if (x==y) {
        seg[node] = val; 
        return; 
    }
    ll mid = (x + y) >> 1; 
    update(pos, val, node << 1, x, mid); 
    update(pos, val, (node << 1) + 1, mid + 1, y); 
    seg[node] = seg[node << 1] + seg[(node << 1) + 1]; 
    return; 
}
 
ll query(int lo, int hi, int node, int x, int y) {
    if (lo > y || hi < x) return 0; 
    if (lo <= x && y <= hi) return seg[node]; 
    ll mid = (x + y) >> 1; 
    ll l = query(lo, hi, node << 1, x, mid); 
    ll r = query(lo, hi, (node << 1) + 1, mid + 1, y);
    return l+r; 
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
 
    cin >> n >> q; 
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    init(1, 1, n); 
    while (q--) {
        int a, b, c, d; 
        cin >> a >> b >> c >> d;
        int a1 = (a > b) ? b : a; int b1 = (a > b) ? a : b; 
        cout << query(a1, b1, 1, 1, n) << '\n'; 
        update(c, d, 1, 1, n);
    }
    return 0; 
}


저작자표시

'PS) BOJ > Segment Tree' 카테고리의 다른 글

[C++] 커피숍2 [백준 1275]  (0) 2018.08.16
[C++]음주 코딩[백준 5676]  (0) 2018.08.16

+ Recent posts

티스토리툴바