반응형

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

 

3151번: 합이 0

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받은 수들을 arr 배열에 저장하고, 오름차순으로 정렬합니다.

 

2. arr를 0부터 N-2까지 for문을 통해 돌면서 start = i+1, end = N-1로 시작하여

 - arr[ i ] + arr[ start ] + arr[ end ]의 값이 0보다 크다면 end--

 - arr[ i ] + arr[ start ] + arr[ end ]의 값이 0보다 작다면 start++

 - 0이라면 분기를 나누어 ans에 값을 더해줍니다.

이때, arr[ i ]의 값이 0보다 크다면 세 수의 합이 0이 될 수 없으므로 반복문을 종료해줍니다.

 

3. 2에서 sum이 0일 때,

 - start와 end의 값이 같다면 end - start + 1개 중 두 개를 뽑는 경우의 수를 ans에 더해주고

 - arr[ start ] == arr[ start + 1]일 때 left++

 - arr[ end ] == arr [ end - 1 ]과 같다면 right++

마지막에 ans에 left * right 를 더해줍니다.

 

4. 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<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int N;
int arr[10000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + N);
 
    ll ans = 0;
 
    for (int i = 0; i < N - 2; i++) {
        int start = i + 1;
        int end = N - 1;
 
        if (arr[i] > 0) break;
 
        while (start < end) {
            int left = 1;
            int right = 1;
            int sum = arr[i] + arr[start] + arr[end];
            if (sum == 0) {
                if (arr[start] == arr[end]) {
                    int temp = end - start;
                    ans += (1LL * temp + 1) * (1LL * temp) / 2;
                    break;
                }
                while (arr[start] == arr[start + 1]) {
                    start++;
                    left++;
                }
                while (arr[end] == arr[end - 1]) {
                    end--;
                    right++;
                }
 
                ans += 1LL * left * right;
                start++;
                end--;
            }
            else if (sum > 0) {
                end--;
            }
            else {
                start++;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
[ 백준 ] 5430번 - AC (C++)  (0) 2023.07.09
[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08
[ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++)  (0) 2023.07.07
반응형

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

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열이 trie에 있는지 체크하고, 있다면 NO를 출력하고, 그렇지 않다면 YES를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, t;
 
struct trie {
    trie* num[10];
    bool end;
 
    trie() {
        end = false;
        for (int i = 0; i < 10; i++) num[i] = NULL;
    }
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if(num[i]) delete num[i];
        }
    }
 
    void insert(const char* ch) {
        if (!*ch) {
            this->end = true;
            return;
        }
 
        int now = *ch - '0';
        if (!num[now]) num[now] = new trie;
        num[now]->insert(ch + 1);
    }
 
    bool find(const char* ch) {
        if (!*ch || end) {
            return true;
        }
 
        int now = *ch - '0';
        if (!num[now]) return false;
        return num[now]->find(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--) {
        trie* root = new trie;
        bool flag = true;
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            char arr[11];
            cin >> arr;
 
            if (root->find(arr)) {
                if(flag) cout << "NO\n";
                flag = false;
            }
            else {
                root->insert(arr);
            }
        }
 
        if (flag) {
            cout << "YES\n";
        }
 
        delete root;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.21
반응형

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

 

3649번: 로봇 프로젝트

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받고, 오름차순으로 정렬합니다.

 

2. while문을 통해 l < r 일 때 arr[ l ] + arr[ r ] 의 값이 x와 같다면 출력하고, x보다 작다면 l++, x보다 크다면 r--를 통해 x와 같을 때까지 반복해 줍니다.

 

3. x와 같은 경우가 없다면 danger를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int x, n;
int arr[1000000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (cin >> x) {
        x *= 10000000;
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
 
        sort(arr, arr + n);
 
        int l = 0;
        int r = n - 1;
        bool flag = false;
 
        while (l < r) {
            if (arr[l] + arr[r] == x) {
                cout << "yes " << arr[l] << ' ' << arr[r];
                flag = true;
                break;
            }
            else if (arr[l] + arr[r] < x) {
                l++;
            }
            else if (arr[l] + arr[r] > x) {
                r--;
            }
        }
 
        if (flag == false) {
            cout << "danger";
        }
 
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1963번 - 소수 경로 (C++)  (0) 2023.06.26
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.21
[ 백준 ] 2830번 - 행성 X3 (C++)  (0) 2023.06.20
반응형

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

 

15789번: CTP 왕국은 한솔 왕국을 이길 수 있을까?

입력의 첫째 줄에 왕국의 수 N(3 ≤ N ≤ 100,000)과 동맹 관계의 수 M(1 ≤ M ≤ 200,000)이 주어진다. 이 후 M개의 줄에 X,Y가 주어진다. 이는 X 왕국과 Y 왕국이 동맹이라는 뜻이다. 입력의 마지막 줄에 CT

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 왕국을 이어주고, 이을 때마다 power 배열에 값을 경신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 CTP 왕국이나 한솔 왕국에 속하지 않은 왕국들의 동맹국들의 수를 ans 배열에 저장합니다.

 

5. ans 배열을 내림차순으로 정렬하고, K개까지 동맹국을 더해줍니다.

 

6. 그 결과를 출력합니다.

 

[ 소스코드 ]

 

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;
 
int N, M;
int vect[100001];
int power[100001];
int visited[100001];
vector<int> ans;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
    power[pa] += power[pb];
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        power[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int X, Y;
        scanf("%d %d", &X, &Y);
 
        if (Find(X) != Find(Y)) {
            Union(X, Y);
        }
    }
 
    int C, H, K;
    scanf("%d %d %d", &C, &H, &K);
    int cnt = 0;
 
    if (K) {
        for (int i = 1; i <= N; i++) {
            int temp = Find(i);
            if ((Find(C) != temp) && (temp != Find(H))) {
                if (visited[temp] == 0) {
                    visited[temp] = 1;
                    ans.push_back({ power[temp] });
                }
            }
        }
    }
 
    sort(ans.begin(), ans.end(), greater<>());
 
    int temp = power[Find(C)];
 
    for (int i = 0; i < min((int)ans.size(), K); i++) {
        temp += ans[i];
    }
    printf("%d", temp);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
반응형

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

 

2513번: 통학버스

첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 좌표와 사람 수의 쌍을 입력받고, 좌표가 S보다 작다면  arr1에, S보다 크다면 arr2에 저장합니다.

 

2. arr1은 좌표를 기준으로 오름차순으로 정렬하고, arr2는 좌표를 기준으로 내림차순으로 정렬합니다.

 

3. 학교를 기준으로 가장 먼 지역부터 버스를 운행해서 해당 좌표에 사람이 K보다 많거나 같다면 왕복 거리를 ans에 더해주고, 나은 사람들을 버스에 태웁니다.

 

4. 3과 마찬가지로 K보다 많거나 같은 사람들을 먼저 처리하고, 버스에 타고 있는 사람 + 현재 좌표에 남은 사람의 수가 K보다 크다면 왕복 거리를 ans에 더해주고, bus의 사람 수를 bus = bus + cnt - K로 저장해 줍니다.

 

5. 3과 4를 반복하고, 마지막에 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N, K, S;
vector<pair<int, int>> arr1;
vector<pair<int, int>> arr2;
 
int main()
{
    scanf("%d %d %d", &N, &K, &S);
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a < S) {
            arr1.push_back({ a,b });
        }
        else {
            arr2.push_back({ a,b });
        }
    }
 
    sort(arr1.begin(), arr1.end());
    sort(arr2.begin(), arr2.end(), greater<>());
 
    int ans = 0;
 
    int bus = 0;
 
    for (auto& next : arr1) {
        const int pos = next.first;
        int cnt = next.second;
 
        if (cnt >= K) {
            ans += (S - pos) * 2 * (int)(cnt / K);
            cnt %= K;
        }
        
        if (cnt > 0) {
            if (bus == 0) {
                ans += (S - pos) * 2;
                bus = cnt;
            }
            else {
                if (bus + cnt > K) {
                    ans += (S - pos) * 2;
                    bus = bus + cnt - K;
                }
                else {
                    bus += cnt;
                }
            }
        }
    }
 
    bus = 0;
 
    for (auto& next : arr2) {
        const int pos = next.first;
        int cnt = next.second;
 
        if (cnt >= K) {
            ans += (pos - S) * 2 * (int)(cnt / K);
            cnt %= K;
        }
 
        if (cnt > 0) {
            if (bus == 0) {
                ans += (pos - S) * 2;
                bus = cnt;
            }
            else {
                if (bus + cnt > K) {
                    ans += (pos - S) * 2;
                    bus = bus + cnt - K;
                }
                else {
                    bus += cnt;
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26
[ 백준 ] 2671번 - 잠수함식별 (C++)  (0) 2023.04.25
[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
반응형

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

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 만들고, 시간을 기준으로 오름차순으로 정렬하되 시간이 같으면 끝나는 시간이 앞으로 오도록 우선순위를 정합니다.

 

2. pq에서 값을 하나씩 꺼내면서 temp에 시작하는 시간이면 1을 더하고, 끝나는 시간이면 1을 빼줍니다.

 

3. temp의 값 중 가장 큰 값을 ans에 저장합니다.

 

4. 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
 
struct Class {
    char cur;
    int time;
};
 
struct cmp {
    bool operator()(Class right, Class left) {
        if (right.time == left.time) {
            if (left.cur == 'e') {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            return left.time < right.time;
        }
    }
};
 
int main()
{
    priority_queue<Class, vector<Class>, cmp> pq;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int S, T;
        scanf("%d %d", &S, &T);
 
        pq.push({ 's', S});
        pq.push({ 'e', T});
    }
 
    int ans = 0;
    int temp = 0;
 
    while (!pq.empty()) {
        const char cur = pq.top().cur;
        pq.pop();
 
        if (cur == 's') temp++;
        else temp--;
 
        ans = max(ans, temp);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 20311번 - 화학 실험 (C++)  (0) 2023.04.21
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
반응형

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

 

20311번: 화학 실험

화학 실험을 하던 윤이는 일렬로 나열해 놓은 $N$개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 시험관의 개수를 입력받고, priority_queue에 내림차순으로 정렬합니다.

 

2. 만약 수가 가장 많은 시험관의 개수가 (N + 1) / 2개보다 많다면 -1을 출력합니다.

 

3. pq에서 값을 하나씩 뽑아 arr 배열에 시험관의 색깔 번호를 넣습니다.

 

4. 0 ~ (N + 1) / 2 - 1까지 arr 배열의 값을 ans의 0부터 2씩 인덱스를 증가시켜 가면서 넣습니다.

 

5. (N + 1) / 2 ~ N - 1까지 arr배열의 값을 ans의 1부터 2씩 인덱스를 증가시켜 가면서 넣습니다.

 

6. 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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, K;
vector<int> arr;
int ans[300000];
 
int main()
{
    priority_queue<pair<int, int>>pq;
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i <= K; i++) {
        int c;
        scanf("%d", &c);
 
        pq.push({ c,i });
    }
 
    if (pq.top().first > (N + 1) / 2) {
        printf("-1");
        return 0;
    }
 
    while (!pq.empty()) {
        const int cnt = pq.top().first;
        const int num = pq.top().second;
        pq.pop();
 
        for (int i = 0; i < cnt; i++) {
            arr.push_back(num);
        }
    }
    
    int num = 0;
 
    for (int i = 0; i < (N + 1) / 2; i++) {
        ans[num] = arr[i];
        num += 2;
    }
 
    num = 1;
 
    for (int i = (N+1)/2; i < N; i++) {
        ans[num] = arr[i];
        num += 2;
    }
 
    for (int i = 0; i < N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 11000번 - 강의실 배정 (C++)  (0) 2023.04.22
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
반응형

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

 

1253번: 좋다

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받고, 오름차순으로 정렬합니다.

 

2. for문을 통해 0부터 N-1까지 돌면서 s = 0, e = N - 1로 설정하고,  s < e인 동안 반복문을 돌면서 arr[ i ] > arr[ s ] + arr[ e ]라면 s++ 아니라면 e--를 해줍니다.

 

3. 만약 i번째 수가 좋은 수라면 ans + 1을 해주고, map을 활용하여 저장해줍니다.

 

4. 다음에 같은 수가 나온다면 반복문을 돌 필요 없이 바로 ans에 1을 더해줍니다.

 

5. 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
#include<iostream>
#include<algorithm>
#include<map>
 
using namespace std;
 
int N;
int arr[2000];
map<int, int> m;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    sort(arr, arr + N);
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        if (m[arr[i]] > 0) {
            ans++;
            continue;
        }
 
        int s = 0;
        int e = N - 1;
 
        while (s < e) {
            if (s == i) {
                s++;
                continue;
            }
            if (e == i) {
                e--;
                continue;
            }
 
            if (arr[i] == arr[s] + arr[e]) {
                m[arr[i]]++;
                ans++;
                break;
            }
            else if (arr[i] > arr[s] + arr[e]) {
                s++;
            }
            else {
                e--;
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1507번 - 궁금한 민호 (C++)  (0) 2023.04.17
[ 백준 ] 2668번 - 숫자고르기 (C++)  (0) 2023.04.16
[ 백준 ] 2749번 - 피보나치 수 3 (C++)  (0) 2023.04.14
[ 백준 ] 2436번 - 공약수 (C++)  (0) 2023.04.13
[ 백준 ] 1484번 - 다이어트 (C++)  (0) 2023.04.12
반응형

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

 

20366번: 같이 눈사람 만들래?

높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받고, 오름차순으로 정렬합니다.

 

2. 이중 for문을 통해 첫 번째 눈사람을 고정시키고, 두 번째 눈사람을 투 포인터를 이용하여 temp에 저장합니다.

 

3. 첫 번째 눈사람과 두 번째 눈사람의 높이 차의 절댓값 중 최솟값을 ans에 저장하고, ans가 0이라면 바로 출력하고 프로그램을 종료시킵니다.

 

4. 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
#include<iostream>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
int N;
int arr[600];
int ans = 2011111111;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    sort(arr, arr + N);
 
    for (int i = 0; i < N ; i++) {
        for (int j = i + 1; j < N ; j++) {
            int H = arr[i] + arr[j];
            int s, e;
            s = i + 1;
            e = N - 1;
            while (s < e) {
                int temp = arr[s] + arr[e];
 
                if (s == i || s == j) {
                    s++;
                    continue;
                }
                if (e == i || e == j) {
                    e--;
                    continue;
                }
 
                ans = min(ans, abs(H - temp));
 
                if (ans == 0) {
                    printf("0");
                    return 0;
                }
 
                if (H - temp > 0) {
                    s++;
                }
                else {
                    e--;
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2436번 - 공약수 (C++)  (0) 2023.04.13
[ 백준 ] 1484번 - 다이어트 (C++)  (0) 2023.04.12
[ 백준 ] 13144번 - List of Unique Numbers (C++)  (0) 2023.04.10
[ 백준 ] 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (C++)  (0) 2023.04.09
[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
반응형

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

 

2230번: 수 고르기

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받고, 오름차순으로 정렬합니다.

 

2. s = N - 2, e = N - 1로 설정하고, arr[ start ] + arr[ end ]의 값이 M보다 크다면 ans와 값을 비교하여 더 작은 값을 ans에 저장하고, e--를 해주고 그렇지 않다면 s--를 해줍니다.

 

3. s 가 0보다 작아질 때 까지 반복해줍니다.

 

4. 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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int N, M;
int arr[100000];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    sort(arr, arr + N);
 
    int s = N-2;
    int e = N - 1;
    int ans = 2000000001;
 
    while (s >= 0) {
        int temp = arr[e] - arr[s];
 
        if (temp >= M) {
            ans = min(ans, temp);
            e--;
        }
        else {
            s--;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 13144번 - List of Unique Numbers (C++)  (0) 2023.04.10
[ 백준 ] 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (C++)  (0) 2023.04.09
[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07
[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05

+ Recent posts

티스토리툴바