BOJ : https://www.acmicpc.net/problem/7453

github : https://github.com/junho0956/Algorithm/blob/master/7453/7453/%EC%86%8C%EC%8A%A4.cpp

 

필요한 설명들을 코드와 함께 주석처리하였습니다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
typedef long long ll;
vector<int> v;
int arr[4][4001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            cin >> arr[j][i];
 
    // N^4 을 한번에 계산하려고 하면 나중에 3중포문+이분탐색을 해야하는데
    // 이는 4000*4000*4000*log4000.. 시간초과가 발생할 수 밖에 없다.
    // N^2 씩 2개로 배열을 반반으로 나눈 후에 가능한 모든 경우의 수를 계산하자
 
    // 1,2번째 배열로 만들 수 있는 모든 경우의 수를 계산
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            v.push_back(arr[0][i] + arr[1][j]);
 
    // 이분탐색을 위해 정렬
    sort(v.begin(), v.end());
 
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int sum = arr[2][i] + arr[3][j];
            // 0을 만들 수 있는 가능한 범위를 lower_bound, upper_bound 를 이용하여 계산
            int lower = lower_bound(v.begin(), v.end(), 0 - sum) - v.begin();
            int upper = upper_bound(v.begin(), v.end(), 0 - sum) - v.begin();
            cnt += upper - lower;
        }
    }
    
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 3474번 교수가 된 현우  (0) 2020.02.02
BOJ 2632번 피자판매  (0) 2020.02.02
BOJ 1208번 부분수열의 합 2  (0) 2020.02.01
BOJ 1261번 알고스팟  (0) 2020.01.31
BOJ 1644번 소수의 연속합  (0) 2020.01.31

BOJ : https://www.acmicpc.net/problem/1208

github : https://github.com/junho0956/Algorithm/blob/master/1208/1208/%EC%86%8C%EC%8A%A4.cpp

 

이 문제를 풀기 전에는 기본적으로 집합의 합의 경우를 구해내는 문제인 

1182번 부분수열의 합 https://junho0956.tistory.com/16을 풀어보시면 좋습니다.

 

부분수열의 합2 문제는 1182번 과는 다르게 범위가 2배 늘어난 문제입니다.

기본적으로 N 이 20이면 백만정도의 범위가 나오는데, N 이 40이 되면 1조가 넘는 계산량이 나오기 때문에

1182번과 같은 방식으로 풀면 시간초과가 날 수 밖에 없습니다.

 

이 문제를 해결하기 위해서는 N이 40인 배열을 반으로 나누는 계산이 필요합니다.

그럼 N이 20인 배열을 2번 계산하면 되기때문에 계산량이 확 줄게되어 문제를 해결할 수 있게 됩니다.

 

반으로 쪼갠 배열들의 이름을 A,B 라고 했을 때

원하는 답인 경우의 수는 3가지 방법으로 접근할 수 있습니다.

1. A의 부분집합의 합 중에서 S를 만들 수 있는 경우

2. B의 부분집합의 합 중에서 S를 만들 수 있는 경우

3. A와 B의 부분집합의 합 중에서 A+B로 S를 만들 수 있는 경우

 

1,2번 방법은 부분집합의 합을 만드는 과정에서 1182번 문제와 같이 경우의 수를 구해주시면 됩니다.

 

3번 방법은 S를 A+B로 만들어야하기때문에

A[i] 로 S를 만들기 위해서는 B에서 S-A[i] 가 존재해야한다는 것을 알 수 있습니다.

이를 이용해서, S-A[i] 를 미리 계산해둔 후에 B의 합의 집합내에서 S-A[i] 를 찾아주시면 됩니다.

 

이분탐색을 이용해서 그 범위를 빠르게 찾아주시면 됩니다.

 

lower_bound => 원하는 키값과 같은 값들의 첫번째 위치 또는 키값이 없을때는 키값보다 첫번째로 큰 위치

(ex : 223335566 에서 lower_bound 3 은 인덱스 2) 

upper_bound => 원하는 키값 기준 처음으로 큰 위치

(ex : 223335566 에서 lower_bound 3,4 은 인덱스 5)

 

S-A[i] 라는 것은 같은 값이 여러개가 존재할 수도 있고, 없을수도 있고, 단 하나만 있을 수도 있습니다.

결국 upper_bound 값 - lower_bound 값을 하게 되면 원하는 S-A[i] 의 값들의 갯수를 알 수 있습니다.

이렇게 3번 방법으로 경우의 수를 구하시면 됩니다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int arr[40];
int N, S;
long long cnt;
vector<int> a, b;
 
void makeA(int idx, int sum) {
    sum += arr[idx];
    if (idx >= N / 2) return;
    // 만약 S를 만들 수 있다면 cnt++을 해준다
    if (sum == S) cnt++;
 
    a.push_back(sum);
    makeA(idx + 1, sum - arr[idx]);
    makeA(idx + 1, sum);
}
 
void makeB(int idx, int sum) {
    sum += arr[idx];
    if (idx >= N) return;
    // 만약 S를 만들 수 있다면 cnt++을 해준다
    if (sum == S) cnt++;
    
    b.push_back(sum);
    makeB(idx + 1, sum - arr[idx]);
    makeB(idx + 1, sum);
}
 
int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    // 벡터 a,b 에 반으로 나눈 각 배열에 대한 만들 수 있는 모든 부분집합의 합들을 미리 구해놓는다
    makeA(0, 0);
    makeB(N / 2, 0);
 
    // 이분탐색을 이용하기 위해서 미리 정렬을 해둔다
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
 
    // 찾고자하는 값의 갯수를 이분탐색을 이용해서 구한다
    for (int i = 0; i < a.size(); i++) {
        int temp = S - a[i];
        int lower = lower_bound(b.begin(), b.end(), temp) - b.begin();
        int upper = upper_bound(b.begin(), b.end(), temp) - b.begin();
        cnt += upper - lower;
    }
 
    cout << cnt;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2632번 피자판매  (0) 2020.02.02
BOJ 7453번 합이 0인 네 정수  (0) 2020.02.01
BOJ 1261번 알고스팟  (0) 2020.01.31
BOJ 1644번 소수의 연속합  (0) 2020.01.31
BOJ 1806번 부분합  (0) 2020.01.31

BOJ : https://www.acmicpc.net/problem/1261

github : https://github.com/junho0956/Algorithm/blob/master/1261/1261/%EC%86%8C%EC%8A%A4.cpp

 

제대로 확인은 해보지 않았지만 

평범한 BFS로 문제를 해결하려하면 모든 범위를 다 확인해야되기 때문에 TLE 에 해당하게 될 것입니다.

(1.1) 에서 (N,M) 으로 최대한 시간내에 갈 수 있는 '최단거리' 를 어떻게 찾아야 할까요?

 

방법은 다익스트라 알고리즘 입니다.

다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 '최단거리' 를 구하는 알고리즘입니다.

 

헷갈리면 안되는 것은

크루스칼이나 프림과는 다르다는 것입니다.

구별하자면 크루스칼 == 프림 != 다익스트라 입니다.

 

크루스칼과 프림은 모든 정점을 서로 이으면서 그 구간이 최단거리가 되는 '도로망' 같은 것을 예를 들 수 있고

다익스트라는 한 정점에서 다른 정점으로의 최단거리 이기 때문에 '네비게이션' 같은 것을 예로 들 수 있겠습니다.

 

이 문제를 해결하기 위해서 사용할 수 있는 방법은 위에서 말한 크루스칼,

그리고 가장 비슷한 방법인 deque 를 이용한 BFS 가 있습니다.

deque 를 이용한 BFS 가 좀더 간편하고 쉬워서 이를 이용해서 문제를 해결하였습니다.

 

deque 를 이용한 BFS 의 가장 큰 특징은 가중치가 0일때 push_front 가중치가 1일때 push_back 한다는 것입니다.

deque 를 이용한 BFS 역시 다익스트라와 거의 유사하게 우선순위큐를 사용하듯이 가중치가 작은 정점을

먼저 사용할 수 있습니다.

 

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
#include <cstdio>
#include <deque>
using namespace std;
#pragma warning(disable:4996)
 
deque<pair<pair<int, int>, int> > dq;
int N, M;
int arr[100][100];
bool visit[100][100];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
 
int main() {
    scanf("%d%d", &M, &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%1d", &arr[i][j]);
 
    dq.push_back({ {0,0},0 });
    while (!dq.empty()) {
        int y = dq.front().first.first;
        int x = dq.front().first.second;
        int cnt = dq.front().second;
        dq.pop_front();
 
        if (visit[y][x]) continue;
        visit[y][x] = true;
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && xx >= 0 && yy < N && xx < M && !visit[yy][xx]) {
                if (arr[yy][xx]) dq.push_back({ {yy,xx},cnt + 1 });
                else dq.push_front({ {yy,xx},cnt });
            }
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 7453번 합이 0인 네 정수  (0) 2020.02.01
BOJ 1208번 부분수열의 합 2  (0) 2020.02.01
BOJ 1644번 소수의 연속합  (0) 2020.01.31
BOJ 1806번 부분합  (0) 2020.01.31
BOJ 2003번 수들의 합2  (0) 2020.01.31

BOJ : https://www.acmicpc.net/problem/1644

github : https://github.com/junho0956/Algorithm/blob/master/1644/1644/%EC%86%8C%EC%8A%A4.cpp

 

N 이 400만까지 나올 수 있다는 것을 무시하고

11번째 코드를 i*i < 4000001; 으로 풀다가 틀리긴 했지만

어렵지않게 해결할 수 있는 문제였습니다.

투포인트 방식을 통해서 좌우를 +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
#include <iostream>
#include <vector>
using namespace std;
 
int arr[4000001];
vector<int> v;
 
int main() {
    for (int i = 0; i < 4000001; i++) arr[i] = true;
 
    for (int i = 2; i < 4000001; i++) {
        if (!arr[i]) continue;
        v.push_back(i);
        for (int k = i + i; k < 4000001; k += i) arr[k] = false;
    }
 
    int N, sum = 0, ans = 0, left = 0, right = 0, len = v.size();
    cin >> N;
 
    while (left <= right && left < len && right <= len) {
        if (v[left] > N) break;
        if (sum == N) ans++;
        if (sum >= N) sum -= v[left++];
        else {
            if (right == len - 1) break;
            sum += v[right++];
        }
    }
 
    cout << ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1208번 부분수열의 합 2  (0) 2020.02.01
BOJ 1261번 알고스팟  (0) 2020.01.31
BOJ 1806번 부분합  (0) 2020.01.31
BOJ 2003번 수들의 합2  (0) 2020.01.31
BOJ 1987번 알파벳  (0) 2020.01.31

+ Recent posts

티스토리툴바