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

github : https://github.com/junho0956/Algorithm/blob/master/12813/12813/%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
#include <cstdio>
#pragma warning(disable:4996)
#define len 100000
 
int main() {
    
    int a[len], b[len];
    for (int i = 0; i < len; i++) scanf("%1d", &a[i]);
    for (int i = 0; i < len; i++) scanf("%1d", &b[i]);
 
    for (int i = 0; i < len; i++) printf("%d", a[i] & b[i]);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", a[i] | b[i]);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", a[i] ^ b[i]);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", a[i] ? 0 : 1);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", b[i] ? 0 : 1);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2098번 외판원 순회  (0) 2020.02.02
BOJ 10971번 외판원 순회2  (0) 2020.02.02
BOJ 2143번 두 배열의 합  (0) 2020.02.02
BOJ 3474번 교수가 된 현우  (0) 2020.02.02
BOJ 2632번 피자판매  (0) 2020.02.02

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

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

 

정올 2001 고등부1번 문제입니다

 

이 문제는 따로 떨어져 있는 경우도 되는 것이 아닌

'부배열' = 연속된 값들로만 해결해야 하는 문제입니다.

makeA, makeB 함수는 연속된 부분집합의 합을 구하는 함수이고, 범위는 1000이기 때문에 충분히 완탐으로 해결됩니다

 

그후에 이분탐색을 이용해서 경우의 수를 구해주시면 됩니다.

 

 

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> va, vb;
int ans, n, m;
int a[1001];
int b[1001];
 
void makeA(int idx, int len) {
    if (idx + len > n) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += a[i];
    va.push_back(sum);
    makeA(idx, len + 1);
}
 
void makeB(int idx, int len) {
    if (idx + len > m) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += b[i];
    vb.push_back(sum);
    makeB(idx, len + 1);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> ans >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i++) cin >> b[i];
 
    for (int i = 0; i < n; i++) makeA(i, 1);
    for (int i = 0; i < m; i++) makeB(i, 1);
 
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
 
    long long cnt = 0;
    for (int i = 0; i < va.size(); i++) {
        int res = ans - va[i];
        int l = lower_bound(vb.begin(), vb.end(), res) - vb.begin();
        int u = upper_bound(vb.begin(), vb.end(), res) - vb.begin();
        cnt += u - l;
    }
 
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 10971번 외판원 순회2  (0) 2020.02.02
BOJ 12813번 이진수 연산  (0) 2020.02.02
BOJ 3474번 교수가 된 현우  (0) 2020.02.02
BOJ 2632번 피자판매  (0) 2020.02.02
BOJ 7453번 합이 0인 네 정수  (0) 2020.02.01

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

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

 

0이라는 수를 만들기 위해서는 2와 5가 필요합니다.

2배수, 5배수씩 소인수분해 해주시면서 곱해지는 2,5 의 갯수를 구해주시면 그중 최솟값이 0의 갯수가 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int f = 0, t = 0, num;
        cin >> num;
 
        for (int i = 2; i <= num; i *= 2)
            t += num / i;
        for (int i = 5; i <= num; i *= 5)
            f += num / i;
 
        int ans = f > t ? t : f;
        cout << ans << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 12813번 이진수 연산  (0) 2020.02.02
BOJ 2143번 두 배열의 합  (0) 2020.02.02
BOJ 2632번 피자판매  (0) 2020.02.02
BOJ 7453번 합이 0인 네 정수  (0) 2020.02.01
BOJ 1208번 부분수열의 합 2  (0) 2020.02.01

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

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

 

문제는 이런식으로 접근해볼 수 있다.

'반드시 연속된 조각' 에서 연속된 부분합에 대한 부분집합이 필요하다

피자는 원형이기때문에 마지막 조각이 첫번째 조각과 연속될 수 있다

각각의 피자에 대한 부분집합을 안다면 이분탐색을 이용하여 경우의 수를 찾을 수 있다

 

연속된 부분합에 대한 부분집합은 범위가 1000 이기 때문에 완전탐색으로도 충분히 구해낼 수 있다

아래 코드에서 makeA, makeB 함수는 완전탐색을 통해 만들어낼 수 있는 부분집합을 구하는 과정인데

범위는 피자의 조각보다 -1 작은 범위까지만 구하고, 마지막에 전체 합에 대한 값만 추가해주면 된다

 

이분탐색을 위해서는 정렬은 필수이고,

 

모든 경우의 수는 피자A, 피자B 각판에서 만들어낼 수 있는 경우의수 + (A+B) 로 만들 수 있는 경우의 수

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
ll cnt;
 
// m,n 의 최대범위는 1000
// 연속된 조각을 판매해야하기 때문에, 원형을 고려해서 2배로 잡는다
int arra[2001], arrb[2001];
vector<int> a, b;
int m, n, k;
 
void makeA(int idx, int len){
    if (len == m) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += arra[i];
    if (sum == k) cnt++;
    a.push_back(sum);
 
    makeA(idx, len + 1);
}
 
void makeB(int idx, int len) {
    if (len == n) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += arrb[i];
    if (sum == k) cnt++;
    b.push_back(sum);
 
    makeB(idx, len + 1);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> k >> m >> n;
    for (int i = 0; i < m; i++) cin >> arra[i], arra[m+i] = arra[i];
    for (int i = 0; i < n; i++) cin >> arrb[i], arrb[n+i] = arrb[i];
 
    // 각 가능한 모든 부분집합의 합들을 구한다
    for (int i = 0; i < m; i++) makeA(i, 1);
    for (int i = 0; i < n; i++)    makeB(i, 1);
    
    // 전체 합을 따로 구한다
    int sum = 0;
    for (int i = 0; i < m; i++) sum += arra[i];
    if (sum == k) cnt++;
    a.push_back(sum), sum = 0;
    for (int i = 0; i < n; i++) sum += arrb[i];
    if (sum == k) cnt++;
    b.push_back(sum);
 
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
 
    // 원하는 피자양을 만들 수 있는 범위를 이분탐색을 이용하여 찾는다
    for (int i = 0; i < b.size(); i++) {
        int res = k - b[i];
        ll lower = lower_bound(a.begin(), a.end(), res) - a.begin();
        ll upper = upper_bound(a.begin(), a.end(), res) - a.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 2143번 두 배열의 합  (0) 2020.02.02
BOJ 3474번 교수가 된 현우  (0) 2020.02.02
BOJ 7453번 합이 0인 네 정수  (0) 2020.02.01
BOJ 1208번 부분수열의 합 2  (0) 2020.02.01
BOJ 1261번 알고스팟  (0) 2020.01.31

+ Recent posts

티스토리툴바