반응형

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

 

17609번: 회문

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받아 str 변수에 저장합니다.

 

2. s = 0, e = str.size() - 1에서 시작하여 s < e 일 때까지 투포인터를 활용하여 단어가 같다면 s++, e--, 단어가 다르다면 erase flag를 통해 지운 지 지우지 않았는지를 체크하고, s++일 때와 e--일 때를 총 두 번 구해줍니다.

 

3. 만약 erase == false, ans == true라면 0을, erase == true, ans == true라면 1을, 둘 다 아니라면 2를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
 
using namespace std;
 
int T;
bool erase;
 
bool check(string str, int num)
{
    int s = 0, e = str.size() - 1;
 
    while (s < e) {
        if (str[s] == str[e]) {
            s++;
            e--;
        }
        else {
            if (!erase) {
                if (num == 1) {
                    if (str[s + 1] == str[e]) {
                        s++;
                        erase = true;
                    }
                }
                else {
                    if (str[s] == str[e - 1]) {
                        e--;
                        erase = true;
                    }
                }
                if (!erase) {
                    return false;
                }
            }
            else {
                return false;
            }
        }
    }
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        erase = false;
        string str;
        cin >> str;
 
        erase = false;
 
        if (check(str, 1)) {
            if (erase) {
                cout << 1;
            }
            else {
                cout << 0;
            }
            cout << '\n';
            continue;
        }
 
        erase = false;
 
        if (check(str, 2)) {
            if (erase) {
                cout << 1;
            }
            else {
                cout << 0;
            }
            cout << '\n';
            continue;
        }
 
        cout << 2;
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
반응형

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

 

16472번: 고냥이

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N과 문자열을 입력받고, 문자의 개수를 저장할 cnt 배열과 총 문자 종류의 개수를 저장할 ch배열을 초기화합니다.

 

2. s = 0, e = 0으로 초기화한 후 e < str.size()인 동안 반복하면서 총 문자 종류의 개수가 N개보다 적거나 같으면 ans에 문자열의 길이의 최댓값을 저장하고, e++, cnt++, 처음 나오는 문자라면 ch++를 해주고, N개보다 많다면 cnt--, s++, 해당 문자의 개수가 0개라면 ch--를 해줍니다.

 

3. 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
#include<iostream>
#include<string>
 
using namespace std;
 
int N;
string str;
int cnt[26];
int ch;
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    cin >> str;
 
    int s = 0;
    int e = 0;
 
    cnt[str[0] - 'a']++;
    ch++;
    ans = 1;
 
    while (e < str.size()) {
        if (ch <= N) {
            ans = max(ans, e - s + 1);
            e++;
            if (cnt[str[e] - 'a'] == 0) ch++;
            cnt[str[e] - 'a']++;
        }
        else {
            cnt[str[s] - 'a']--;
            if (cnt[str[s] - 'a'] == 0) ch--;
            s++;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20182번 - 골목 대장 호석 - 효율성 1 (C++)  (0) 2023.08.14
[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
반응형

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

 

9024번: 두 수의 합

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 입력받고, 두 정수의 합과 K의 차의 절댓값의 최댓값은 $3 \times 10^{8}$ 이므로 min을 322,222,222로 초기화해 줍니다.

 

2. s = 0, e = n - 1로 초기화한 후 s < e인 동안 반복하면서 두 정수의 합과 K의 차의 절댓값이 min보다 작으면 ans = 1로 초기화하고, 절댓값이 min과 같다면 ans++를 해줍니다.

 

3. 이후 K가 두 정수의 합보다 크다면 s++, 아니라면 e--를 해줍니다.

 

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
#include<iostream>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
int t, n, K;
int arr[1000000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    for (int T = 0; T < t; T++) {
        cin >> n >> K;
 
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
 
        sort(arr, arr + n);
 
        int s = 0;
        int e = n - 1;
        int ans = 0;
        int min = 322222222;
 
        while (s < e) {
            int temp = arr[s] + arr[e];
 
            if (abs(temp - K) < min) {
                ans = 1;
                min = abs(temp - K);
            }
            else if (abs(temp - K) == min) {
                ans++;
            }
 
            if (K > temp)s++;
            else e--;
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20168번 - 골목 대장 호석 - 기능성 (C++)  (0) 2023.08.13
[ 백준 ] 16472번 - 고냥이 (C++)  (0) 2023.08.12
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
반응형

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

 

7453번: 합이 0인 네 정수

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수들을 입력받아 arr 배열에 저장하고, arr 배열에서 두 수를 뽑아 더한 값을 sum 배열에 저장합니다. 

 

2. sum 배열을 오름차순으로 정렬합니다.

 

3. 이중 for문을 이용하여 i = N - 1부터 0까지, j는 0부터 N까지 탐색하면서 arr[ i ] + arr[ j ]가 sum 배열에 존재하는지 lower_bound를 활용하여 찾아줍니다.

 

4. sum 배열에 존재한다면 upper_bound를 활용하여 같은 수가 있다면 그 개수만큼 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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int arr[4][4000];
vector<int> sum;
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> arr[j][i];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum.push_back(arr[0][i] + arr[1][j]);
        }
    }
 
    sort(sum.begin(), sum.end());
 
    ll ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp = arr[2][i] + arr[3][j];
 
            auto it = lower_bound(sum.begin(), sum.end(), -temp);
 
            if (*it == -temp) {
                ans += upper_bound(sum.begin(), sum.end(), -temp) - it;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 2295번 - 세 수의 합 (C++)  (0) 2023.07.14
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
반응형

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/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/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/1484

 

1484번: 다이어트

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 최고 몸무게가 G가 될 때까지 반복문을 돌아주면서 현재 몸무게의 제곱 - 기억하는 몸무게의 제곱의 값이 G보다 크다면 s++, G보다 작다면 e++을 해주면서 G와 값이 같다면 ans에 e값을 넣어줍니다.

 

2. ans의 사이즈가 0이라면 -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<iostream>
#define ll long long
#include<vector>
 
using namespace std;
 
ll G;
vector<ll> ans;
 
int main()
{
    scanf("%lld", &G);
 
    ll s = 1;
    ll e = 2;
 
    while (e < G) {
        ll cur = e * e;
        ll before = s * s;
 
        if (cur - before == G) {
            ans.push_back(e);
            e++;
        }
        else if (cur - before > G) {
            s++;
        }
        else {
            e++;
        }
    }
 
    if (ans.size() == 0) {
        printf("-1");
        return 0;
    }
 
    for (auto& next : ans) {
        printf("%lld\n", next);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2749번 - 피보나치 수 3 (C++)  (0) 2023.04.14
[ 백준 ] 2436번 - 공약수 (C++)  (0) 2023.04.13
[ 백준 ] 20366번 - 같이 눈사람 만들래? (C++)  (0) 2023.04.11
[ 백준 ] 13144번 - List of Unique Numbers (C++)  (0) 2023.04.10
[ 백준 ] 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (C++)  (0) 2023.04.09
반응형

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/13144

 

13144번: List of Unique Numbers

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받습니다.

 

2. s = 0, e = 0으로 설정한 후, check 배열을 만들어 check[ arr[ e ] ]++를 통해 같은 수가 있는지 없는지 확인합니다.

 

3. s <= e && e < N일 동안 반복해주면서 check[ arr[ e ] ]<= 1 일 때 e++ 그렇지 않다면 s++을 해주면서 ans += e - s + 1을 통해 ans를 갱신해줍니다. (연속된 수열의 길이가 N일 때 해당 수열의 가장 첫번째 요소를 포함한 부분 수열의 개수는 N개이므로)

 

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
int arr[100000];
int check[100001];
int s, e;
ll ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    check[arr[s]] = 1;
 
    while (s <= e && e < N) {
 
        if (check[arr[e]] <= 1) {
            ans += e - s + 1;
        }
 
        if (check[arr[e]] > 1) {
            check[arr[s]]--;
            s++;
        }
        else {
            e++;
            check[arr[e]]++;
        }
 
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1484번 - 다이어트 (C++)  (0) 2023.04.12
[ 백준 ] 20366번 - 같이 눈사람 만들래? (C++)  (0) 2023.04.11
[ 백준 ] 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (C++)  (0) 2023.04.09
[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07

+ Recent posts

티스토리툴바