반응형

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

 

1354번: 무한 수열 2

첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map< ll, ll> um을 선언합니다.

 

2. 재귀함수를 통해 n이 0보다 작거나 같으면 1을 return하고, um.count(n)이 0일 때 um[ n ] = dfs(n / P) + dfs(n / Q)를 통해 um[ n ]을 구해줍니다.

 

3. dfs(N)을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
ll N;
int P, Q, X, Y;
unordered_map<ll, ll> um;
 
ll dfs(ll n)
{
    if (n <= 0) return um[n] = 1;
    if (um.count(n) != 0) return um[n];
 
    return um[n] = dfs(n / P - X) + dfs(n / Q - Y);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> P >> Q >> X >> Y;
 
    cout << dfs(N);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04
[ 백준 ] 1461번 - 도서관 (C++)  (0) 2023.10.03
[ 백준 ] 2174번 - 로봇 시뮬레이션 (C++)  (0) 2023.10.01
[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
[ 백준 ] 9177번 - 단어 섞기 (C++)  (0) 2023.09.29
반응형

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

 

1351번: 무한 수열

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. unordered_map< ll, ll> um을 선언하고, um[ 0 ] = 1로 초기화합니다.

 

2. 재귀함수를 통해 um.count(n)이 0일 때 um[ n ] = dfs(n / P) + dfs(n / Q)를 통해 um[ n ]을 구해줍니다.

 

3. dfs(N)을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
ll N;
int P, Q;
unordered_map<ll, ll> um;
 
ll dfs(ll n)
{
    if (um.count(n)) return um[n];
 
    return um[n] = dfs(n / P) + dfs(n / Q);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> P >> Q;
 
    um[0] = 1;
 
    cout << dfs(N);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
[ 백준 ] 9177번 - 단어 섞기 (C++)  (0) 2023.09.29
[ 백준 ] 14925번 - 목장 건설하기 (C++)  (0) 2023.09.27
[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)  (0) 2023.09.26
[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
반응형

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

 

2015번: 수들의 합 4

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 배열의 1번부터 N번까지 수를 입력받으면서 누적합을 arr 배열에 저장하고, unordered_map<int, long long> um 자료구조에 누적합의 개수를 저장합니다.

 

2. ans에 um[ arr[ i ] - K ] 의 개수를 더해줍니다.

 

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
#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
int N, K;
int arr[200001];
unordered_map<int, ll> um;
ll ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K;
 
    um[0] = 1;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        arr[i] += arr[i - 1];
 
        ans += um[arr[i] - K];
 
        um[arr[i]]++;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10835번 - 카드게임 (C++)  (0) 2023.09.25
[ 백준 ] 3197번 - 백조의 호수 (C++)  (0) 2023.09.24
[ 백준 ] 13565번 - 침투 (C++)  (0) 2023.09.22
[ 백준 ] 12761번 - 돌다리 (C++)  (0) 2023.09.21
[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
반응형

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

 

16934번: 게임 닉네임

첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고,

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/417

 

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

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

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 print를 통해 새로운 문자가 나오거나 문자열의 끝이 오면 해당 문자열을 출력합니다.

 

2. trie에 해당 문자열을 insert 합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
 
struct Trie {
    Trie* arr[26];
    int end;
 
    Trie() {
        for (int i = 0; i < 26; i++) {
            arr[i] = NULL;
        }
 
        end = 0;
    }
 
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (arr[i]) delete arr[i];
        }
    }
 
    void insert(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            end++;
            return;
        }
 
        if (arr[temp] == NULL) arr[temp] = new Trie;
        arr[temp]->insert(ch + 1);
    }
 
    void print(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            if (end) {
                cout << end + 1;
            }
            cout << '\n';
            return;
        }
 
        cout << *ch;
 
        if (arr[temp] == NULL) {
            cout << '\n';
            return;
        }
 
        arr[temp]->print(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    Trie* root = new Trie;
 
    for (int i = 0; i < N; i++) {
        char ch[11];
        cin >> ch;
 
        root->print(ch);
        root->insert(ch);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15558번 - 점프 게임 (C++)  (0) 2023.07.27
[ 백준 ] 1245번 - 농장 관리 (C++)  (0) 2023.07.26
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
반응형

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

 

2295번: 세 수의 합

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

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

 

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

 

4. sum 배열에 존재한다면 해당 수가 최댓값이므로 arr[ i ]를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[1000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    vector<int> sum;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            sum.push_back(arr[i] + arr[j]);
        }
    }
 
    sort(arr, arr + N);
    sort(sum.begin(), sum.end());
 
    int ans = 0;
 
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            if (*lower_bound(sum.begin(), sum.end(), arr[i] - arr[j]) == arr[i]-arr[j]) {
                cout << arr[i];
                return 0;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
반응형

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

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 rel 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. unordered_map 자료 구조를 활용하여 해당 친구의 인덱스를 저장합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 rel 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#include<string>
 
using namespace std;
 
int vect[200001];
int rel[200001];
unordered_map<string, int> m;
 
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;
    rel[pa] += rel[pb];
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int F;
        int cnt = 1;
        m.clear();
        scanf("%d", &F);
 
        for (int i = 1; i <= F * 2; i++) {
            vect[i] = i;
            rel[i] = 1;
        }
 
        for (int i = 0; i < F; i++) {
            char A[21];
            char B[21];
            scanf("%s %s", A, B);
 
            if (m.count(A) == 0) {
                m[A] = cnt++;
            }
            if (m.count(B) == 0) {
                m[B] = cnt++;
            }
 
            int a = m[A];
            int b = m[B];
 
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
 
            printf("%d\n", rel[Find(a)]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27
반응형

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

+ Recent posts

티스토리툴바