반응형

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

 

17436번: 소수의 배수

첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제에서는 포함 배제의 원리를 활용해 문제를 풀어야 하므로 다음 글을 일고 오시면 좋습니다!

 

https://rudalsd.tistory.com/47?category=1064608 

 

[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)

오늘은 포함 배제의 원리(Inclusion-exclusion principle)에 대해 설명드리겠습니다. 유한한 집합의 합집합의 총 원소의 개수를 세는 방법입니다. [ 동작 원리 ] 즉, 겹치는 집합의 개수가 홀수이면 해당

rudalsd.tistory.com

 

N의 최댓값이 10이므로 모든 경우의 수를 생각해도 O(2^10)이므로 0.25초 안에 충분히 풀 수 있습니다.

 

배열에 소수들을 저장하고, 각 조합의 소수들을 모두 곱한 값으로 M을 나누어 준 몫을 답에 더해주거나 빼주면 됩니다. M보다 작은 값들 중 나누어 떨어지는 수가 몫의 개수만큼 있다는 뜻이기 때문입니다. 만약 조합의 개수가 홀수라면 더해주고, 짝수라면 빼주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
long long M;
int arr[10];
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    long long ans = 0;
 
    for (int i = 1; i < (1 << N); i++) {
        int cnt = 0;
        long long num = 1;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) {
                cnt++;        //몇 개의 소수가 곱해져 있는지
                num *= arr[j];    //소수들을 곱함
            }
        }
 
        if (cnt % 2 == 1) {
            ans += M / num;        //M을 소수들을 모두 곱한 값으로 나눈 값을 더함
        }
        else {
            ans -= M / num;        //M을 소수들을 모두 곱한 값으로 나눈 값을 뺌
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
반응형

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

 

16565번: N포커

첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제에서는 포함 배제의 원리를 활용해 문제를 풀어야 하므로 다음 글을 일고 오시면 좋습니다!

 

https://rudalsd.tistory.com/47?category=1064608 

 

[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)

오늘은 포함 배제의 원리(Inclusion-exclusion principle)에 대해 설명드리겠습니다. 유한한 집합의 합집합의 총 원소의 개수를 세는 방법입니다. [ 동작 원리 ] 즉, 겹치는 집합의 개수가 홀수이면 해당

rudalsd.tistory.com

 

먼저 모든 조합의 개수를 dp를 이용하여 구해줍니다. iCj = i-1Cj-1 + i-1Cj라는 점화식을 이용하여 구해주면 쉽게 구할 수 있습니다.

 

comb [ i ][ j ] = comb [ i - 1 ][ j - 1 ] + comb [ i - 1 ][ j ];

 

이를 통해서 포카드가 1개 이상일 때, 2개 이상일 때, 3개 이상일 때 ··· 13개 이상일 때의 조합의 개수를 각각 더해주거나 빼주면서 답을 구하면 됩니다.

 

포함 배제의 원리를 이용하여 포카드의 개수가 홀수일 때는 더해주고, 짝수일 때는 빼주면 답을 구할 수 있습니다.

 

[ 소스 코드 ]

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 MOD 10007
 
using namespace std;
 
int comb[53][53];
int N;
 
int main()
{
    for (int i = 0; i < 53; i++) {            //iCj의 조합을 dp를 활용해서 미리 구해 놓음
        for (int j = 0; j <= i; j++) {
            if (i == j || j == 0) {
                comb[i][j] = 1;
            }
            else if (j == 1) {
                comb[i][j] = i;
            }
            else {
                comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
            }
        }
    }
 
    cin >> N;
    int ans = 0;
 
    for (int i = 1; i <= N / 4; i++) {    //포함 배제의 원리
        if (i % 2 == 1) {        //포카드 조합이 홀수일 때
            ans += (comb[13][i] * comb[52 - 4 * i][N - 4 * i]) % MOD;
        }
        else {                    //포카드 조합이 짝수일 때
            ans -= (comb[13][i] * comb[52 - 4 * i][N - 4 * i]) % MOD;
        }
        ans = (ans + MOD) % MOD;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
[ 백준 ] 17436번 - 소수의 배수 (C++)  (0) 2022.07.02
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
반응형

오늘은 포함 배제의 원리(Inclusion-exclusion principle)에 대해 설명드리겠습니다. 유한한 집합의 합집합의 총 원소의 개수를 세는 방법입니다.

 

[ 동작 원리 ]

 

 

즉, 겹치는 집합의 개수가 홀수이면 해당 집합의 개수를 더하고, 짝수라면 해당 집합의 개수를 빼면 됩니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem)  (0) 2022.07.10
[ 알고리즘 ] 오일러 피 함수(Euler's phi function)  (0) 2022.07.09
[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)  (0) 2022.06.29
[ 알고리즘 ] 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)  (0) 2022.06.21
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)  (0) 2022.06.11
반응형

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

 

15824번: 너 봄에는 캡사이신이 맛있단다

한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제에서는 모듈러 연산이 필요하므로 다음 글을 읽고 오시면 좋습니다!

 

https://rudalsd.tistory.com/45?category=1064608 

 

[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)

오늘은 모듈러 연산에 대해 설명드리겠습니다. 특정 수 M을 넘는 수에 모듈러 연산을 하려면 어떻게 해야 할까요? 모듈러 연산의 특성을 활용하면 쉽게 구할 수 있습니다. [ 동작 원리 ] 정수 A와

rudalsd.tistory.com

 

어떤 한 수가 조합 내에서 최댓값이 될 때의 개수와 최솟값이 될 때의 개수를 통해 쉽게 정답을 구할 수 있습니다.

 

먼저 입력받은 수를 오름차순으로 정렬한 후 for문을 돌면서 그 수가 최댓값이 될 때의 조합의 개수는 그 수보다 작은 수의 개수가 i일 때 2^i가 됩니다. 

 

마찬가지로 그 수가 최솟값이 될 때의 조합의 개수는 그 수보다 큰 수의 개수가 j일 때 2^j가 됩니다.

 

따라서 모든 수에 대해 (2^i - 2^j) * a를 구해서 더해주면 됩니다.

 

하지만 n의 최댓값이 300,000이므로 일반적인 방법으로는 2^300,000의 수를 구하기는 쉽지 않습니다. 따라서 분할 정복을 활용하여 답을 구해줍니다.

 

[ 소스 코드 ]

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<cstring>
 
#define MOD 1000000007
 
using namespace std;
 
int N;
long long arr[300001];
long long comb[300001];
long long ans;
 
long long Comb(int n)        //분할 정복을 통한 2의 n승 구하기
{
    if (comb[n] != -1) return comb[n];
    if (n % 2 == 0) {
        return comb[n] = ((Comb(n / 2) % MOD) * (Comb(n / 2) % MOD)) % MOD;
    }
    else {
        return comb[n] = ((Comb(n - 1) % MOD) * (Comb(1) % MOD)) % MOD;
    }
}
 
int main()
{
    cin >> N;
    memset(comb, -1, sizeof(comb));
    comb[0] = 1;
    comb[1] = 2;
 
    for (int i = 0; i < N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    sort(arr, arr + N);
 
    for (int i = 0; i < N; i++) {        //arr[i]가 최대가 되는 조합의 개수에서 arr[i]가 최소가 되는 조합의 개수를 빼고
        ans += ((Comb(i) - Comb(N - i - 1) + MOD) % MOD) * (arr[i] % MOD);    //거기에 arr[i]를 곱한 것을 ans에 더함
        ans %= MOD;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17436번 - 소수의 배수 (C++)  (0) 2022.07.02
[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
반응형

오늘은 모듈러 연산에 대해 설명드리겠습니다. 특정 수 M을 넘는 수에 모듈러 연산을 하려면 어떻게 해야 할까요?

 

모듈러 연산의 특성을 활용하면 쉽게 구할 수 있습니다.

 

[ 동작 원리 ]

 

정수 A와 B를 M으로 나눈 나머지를 각각 a, b라고 한다면, 이때 A+B를 M으로 나눈 나머지는 얼마일까요?

 

A = xM + a

B = yM + b

A + B = (x + y)M + (a + b)

(A + B)%M = (a + b)%M

 

따라서, (A + B)%M = ((a%M) + (b%M))%M이라는 결과가 나옵니다. 이러한 성질은 덧셈, 뺄셈, 곱셈에 모두 성립합니다.

 

하지만 음수에 모듈러를 적용하면 다음과 같은 결과가 나옵니다.

 

-9 % 11 = 2

-5 % 11 = 6

-23 % 11 = 10

=>

(23%11) = 1

-1 + 11 = 10

 

따라서 음수는 양수로 바꾼 값을 M으로 나눈 값을 다시 음수로 바꿉니다. 그 후 그 값에 M의 값을 더해주면 음수에 모듈러를 계산한 값이 나오게 됩니다. 나눗셈을 제외한 모듈러 연산은 다음과 같이 정의할 수 있습니다.

 

(A + B)%M = ((a%M) + (b%M))%M

(A - B)%M = ((a%M) - (b%M) + M)%M

(A * B)%M = ((a%M) * (b%M))%M

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 오일러 피 함수(Euler's phi function)  (0) 2022.07.09
[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)  (0) 2022.06.30
[ 알고리즘 ] 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)  (0) 2022.06.21
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)  (0) 2022.06.11
[ 알고리즘 ] 벨만 포드 알고리즘(Bellman-Ford Algorithm)  (0) 2022.06.08
반응형

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

 

13334번: 철로

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

선분의 최대 개수가 100,000개이므로 2중 for문을 돌리게 된다면 시간 초과가 뜹니다. 따라서 한 번의 탐색으로 답을 구해야 합니다.

 

먼저 선분을 끝점의 좌표를 기준으로 오름차순으로 정렬합니다. 그리고 앞에서부터 탐색을 시작하면서 선분의 길이가 d보다 작거나 같다면 priority_queue에 넣어줍니다. 그리고 끝 점의 좌표를 o라고 했을 때 o-d의 좌표보다 시작점의 좌표가 작다면 priority_queue에서 pop을 해줍니다.

 

이때 priority_queue의 size가 선분의 개수가 되고 위의 과정을 반복하면서 size의 최댓값을 저장해줍니다. 그리고 마지막에 최댓값을 출력해주면 쉽게 풀리는 문제였습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct line {
    int h;
    int o;
};
 
struct cmp {        //priority_queue는 선분의 시작 좌표가 작을수록 먼저 나오도록 설정
    bool operator()(line right, line left)
    {
        if (left.h == right.h) return left.o < right.o;
        return left.h < right.h;
    }
};
 
bool comp(line left, line right)    //선분들을 끝 좌표를 기준으로 오름차순 정렬
{
    if (left.o == right.o) return left.h < right.h;
    return left.o < right.o;
};
 
int n, d;
vector<line> arr;
priority_queue<line, vector<line>, cmp> pqAns;
 
int main()
{
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int h, o;
        scanf("%d %d", &h, &o);
        if (h < o) {        //좌푯값이 더 작은 값을 먼저 넣기
            arr.push_back({ h,o });
        }
        else {
            arr.push_back({ o,h });
        }
    }
 
    sort(arr.begin(), arr.end(), comp);
 
    cin >> d;
 
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        int h = arr[i].h;
        int o = arr[i].o;
 
        if (o - h <= d) {    //선분의 길이가 d를 넘지 않으면 push
            pqAns.push({ h,o });
        }
 
        while (!pqAns.empty())
        {
            int h = pqAns.top().h;
            if (h < o - d) {    //만약 제일 앞에 있는 선분이 길이L을 벗어나면 pop
                pqAns.pop();
            }
            else {
                break;
            }
        }
 
        if (ans < pqAns.size()) {    //pq의 사이즈가 선분의 개수
            ans = pqAns.size();
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
반응형

 

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

 

14725번: 개미굴

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

트라이의 개념을 모른다면 공부하고 이 문제를 푸는 것을 추천합니다!

 

문제의 조건에서 사전 순으로 출력하라고 했으므로 map 자료구조를 이용해서 문제를 풀었습니다. 각각의 노드들은 자식 노드를 가지고 있고, 자식 노드들의 키값은 string입니다. 따라서 map <string, Trie*> map을 만들어 주고 이 노드는 자식 노드의 정보를 포인터의 형식으로 가지고 있습니다.

 

먹이를 벡터로 입력 받아서 만약 해당 깊이에 단어가 존재한다면 그 단어의 자식 노드로 넘어가고, 없다면 단어를 동적 할당을 통해 생성해줍니다. 그러고 나서 자식 노드로 넘어가게 됩니다.

 

이러한 방식으로 모든 입력을 처리하면 map의 특성상 자동으로 오름차순으로 정렬이 되기때문에 따로 정렬해줄 필요 없이 Find 함수를 통해서 출력해주면 됩니다.

 

Find 함수 또한 iiterator를 차례로 순회해주면서 dfs와 비슷한 방식으로 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<string>
#include<map>
#include<vector>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie*> m;        //오름차순으로 출력하기 위해서 map을 씀
    ~Trie() {                    //소멸자로 동적 할당한 Trie들을 delete
        for (auto it = m.begin(); it != m.end(); it++) {
            delete it->second;
        }
    }
 
    void Insert(vector<string> vect, int idx)
    {
        if (vect.size() == idx) return;    //모두 삽입했다면 return
 
        if (m.find(vect[idx]) == m.end()) {    //vect[idx]가 map에 없다면
            m.insert({ vect[idx], new Trie });
        }
 
        m[vect[idx]]->Insert(vect, idx + 1);    //다음 단어를 삽입
    }
 
    void Find(int depth)
    {
        for (auto it = m.begin(); it != m.end(); it++) {
            for (int i = 0; i < depth; i++) {
                printf("--");
            }
            cout << it->first << '\n';
            
            it->second->Find(depth + 1);
        }
    }
};
 
int main()
{
    Trie *root = new Trie();
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        vector<string> vect(n);
        for (int j = 0; j < n; j++) {
            cin >> vect[j];
        }
 
        root->Insert(vect, 0);
    }
 
    root->Find(0);
    delete root;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
반응형

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

 

2533번: 사회망 서비스(SNS)

첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제의 조건은 사이클이 없는 트리이기 때문에 주어지는 양방향 그래프를 단방향 트리로 먼저 바꾸어야 합니다. 그 후 dfs와 dp를 활용하여 문제를 풀어주면 됩니다.

 

먼저 각 노드별로 상태가 2가지(얼리어답터이거나 아니거나)씩 있습니다. 이를 활용하여 만약 현재 노드가 얼리어답터라면 다음 노드가 얼리어답터이든 아니든 큰 상관이 없습니다. 하지만 현재 노드가 얼리어답터가 아니라면 다음 노드는 무조건 얼리어답터이어야 합니다.

 

위의 조건을 이용하여 모든 노드들을 체크하면 최종 min(dfs(1,0), dfs(1,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
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
#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
 
vector<int> list[1000001];
vector<int> tree[1000001];
int dp[1000001][2];
int visited[1000001];
int N;
int ans = 987654321;
 
int dfs(int node, int state)        //상태에 따라 최솟값을 저장
{
    if (dp[node][state] != -1) return dp[node][state];
    dp[node][state] = state;
 
    if (state == 0) {
        for (int i = 0; i < tree[node].size(); i++) {
            int next = tree[node][i];
            dp[node][state] += dfs(next, 1);
        }
    }
    else {
        for (int i = 0; i < tree[node].size(); i++) {
            int next = tree[node][i];
            dp[node][state] += min(dfs(next, 0), dfs(next, 1));
        }
    }
 
    return dp[node][state];
}
 
void makeTree(int node)        //그래프를 트리로 재설정
{
    visited[node] = 1;
 
    for (int i = 0; i < list[node].size(); i++) {
        int next = list[node][i];
        if (visited[next] != 1) {
            tree[node].push_back(next);
            makeTree(next);
        }
    }
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    makeTree(1);
 
    memset(dp, -1, sizeof(dp));
 
    int ans = min(dfs(1, 0), dfs(1, 1));
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
반응형

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

 

2162번: 선분 그룹

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/5

 

[ 백준 ] 17387번 - 선분 교차 2 (C++)

https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net [ 문제풀이 ] 선분이 교차할..

rudalsd.tistory.com

 

위 문제를 풀어보고 오는 것을 추천드립니다!

 

이 문제는 선분 교차 2 문제에서 Union - Find를 추가한 문제입니다. 직선의 개수가 3000개밖에 되지 않으므로 2중 for문을 돌려도 큰 문제가 없으므로 2중 for문으로 문제를 풀었습니다. 선분이 교차한다면 Union을 해주고 마지막에 모든 선분을 돌면서 Find를 통해 map에 부모 노드를 저장해줍니다.

 

그리고 map.size()와 map[ 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
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
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <algorithm>
#include<unordered_map>
 
using namespace std;
 
struct pos {
    int x;
    int y;
};
 
pos arr[6000];
int vect[3001];
unordered_map<int, int> m;
 
int N;
 
int Find(int n)
{
    if (vect[n] == n) return n;
    return vect[n] = Find(vect[n]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    if (pa != pb) {
        vect[pb] = pa;
    }
}
 
bool cmp(pos left, pos right)
{
    if (left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    int cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N * 2; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    for (int i = 0; i < N ; i++) {
        sort(arr + i * 2, arr + (i + 1) * 2, cmp);
    }
 
    for (int i = 0; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int l1 = closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2]) * closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2 + 1]);
            int l2 = closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2]) * closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2 + 1]);
            if (l1 == 0 && l2 == 0) {            //두 선이 일직선상에 있을 때
                if (cmp(arr[j*2], arr[i*2+1]) && cmp(arr[i*2], arr[j*2+1])) {
                    if (Find(i) != Find(j)) {
                        Union(i, j);
                    }
                }
            }
            else if (l1 <= 0 && l2 <= 0) {
                if (Find(i) != Find(j)) {
                    Union(i, j);
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        m[Find(i)]++;        //집합에 속해있다면 선분을 map에 추가
    }
 
    int ans = 0;
 
    for (auto it = m.begin(); it != m.end(); it++) {
        if (ans < it->second) {    //집합 중 가장 큰 집합을 ans에 대입
            ans = it->second;
        }
    }
 
    cout << m.size() << endl << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
반응형

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

 

2568번: 전깃줄 - 2

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/35?category=1064612 

 

[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,00..

rudalsd.tistory.com

 

위의 문제와 답을 구하는 과정은 똑같지만 결과를 출력하는 방법이 조금 달랐습니다. 이번 문제는 LIS에 포함되지 않는 수의 개수와 포함되지 않는 수들을 오름차순으로 출력하는 문제였습니다.

 

출력 전까지는 위의 문제와 똑같은 방법으로 문제를 풀어나가지만 마지막에 원하는 index가 아닐 때 ans에 숫자를 push 해줍니다.

 

[ 소스 코드 ]

 

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
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
int N;
map<int, int> A;        //전깃줄이 연결된 번호
map<int, int> idx;        //LIS에서의 index를 저장할 map
vector<int> LIS;
vector<int> ans;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        A[a] = b;
    }
 
    for (auto it = A.begin(); it != A.end(); it++) {
        if (LIS.size() == 0) {
            LIS.push_back(it->second);
            idx[it->first] = 1;
        }
        else {
            if (*LIS.rbegin() < it->second) {
                LIS.push_back(it->second);
                idx[it->first] = LIS.size();
            }
            else {
                int a = lower_bound(LIS.begin(), LIS.end(), it->second) - LIS.begin();
                LIS[a] = it->second;
                idx[it->first] = a + 1;
            }
        }
    }
 
    int cnt = LIS.size();
 
    for (auto it = idx.rbegin(); it != idx.rend(); it++) {
        if (it->second == cnt) {        //뒤에서부터 LIS index를 하나씩 줄여가면서
            cnt--;
        }
        else {                    //원했던 index와 다르다면 ans에 push
            ans.push_back(it->first);
        }
    }
 
    printf("%d\n", ans.size());        //없애야하는 전깃줄의 개수 출력
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%d\n", ans[i]);        //뒤에서부터 ans에 저장된 전깃줄 출력
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22

+ Recent posts

티스토리툴바