반응형

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

간단한 점화식을 만들어서 푸는 문제였습니다.

 

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

 

2. 점화식을 세워 메모이제이션을 통해 최댓값을 저장합니다.

 

3. 마지막 줄의 메모이제이션이 된 수들 중 가장 큰 수를 출력합니다.

 

위의 2번에서 세운 점화식은 다음과 같습니다.

 

dp[ 0 ][ i ] = max( dp[ 1 ][ i - 1 ], dp[ 1 ][ i - 2 ] ) + arr[ 0 ][ i ];

dp[ 1 ][ i ] = max( dp[ 0 ][ i - 1 ], dp[ 0 ][ i - 2 ] ) + arr[ 1 ][ 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
#include<iostream>
 
using namespace std;
 
int arr[2][100002];
int dp[2][100002];
 
int main()
{
    int t;
    scanf("%d", &t);
 
    for (int T = 0; T < t; T++) {
        int n;
        scanf("%d", &n);
 
        for (int i = 0; i < 2 ; i++) {
            for (int j = 2; j <= n+1; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        for (int i = 2; i <= n+1; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + arr[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + arr[1][i];
        }
 
        int ans = 0;
 
        ans = max(dp[0][n+1], dp[1][n+1]);
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
반응형

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

 

1932번: 정수 삼각형

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

간단한 점화식을 만들어서 푸는 문제였습니다.

 

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

 

2. 점화식을 세워 메모이제이션을 통해 최댓값을 저장합니다.

 

3. 마지막 줄의 메모이제이션 된 수들 중 가장 큰 수를 출력합니다.

 

위의 2번에서 세운 점화식은 다음과 같습니다.

 

dp[ i ][ j ] = max( dp[ i - 1 ][ j - 1 ], dp[ i - 1 ][ j ] ) + arr[ i ][ j ]

 

[ 소스 코드 ]

 

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
#include<iostream>
 
using namespace std;
 
int n;
int arr[500][500];
int dp[500][500];
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dp[0][0] = arr[0][0];
 
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + arr[i][0];
    }
 
    int ans = dp[n - 1][0];
 
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
        }
    }
 
    for (int i = 1; i < n; i++) {
        ans = max(ans, dp[n - 1][i]);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
반응형

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

 

17401번: 일하는 세포

출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/38

 

[ 백준 ] 12850번 - 본대 산책2 (C++)

https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net [ 문제풀이 ] 준영이가 정보관에서 1분 후 이동할 수 있는 건물은 전..

rudalsd.tistory.com

 

위 글의 문제 풀이 방식과 매우 비슷하지만 행렬이 매번 바뀌고, 바뀐 행렬에 따라 풀이 방법이 달라집니다.

 

1. 각각의 행렬을 모두 곱한 all 행렬과 나머지 행렬들을 곱한 remain 행렬을 만듭니다.

 

2. 분할 정복을 통해 구한 ans와 remain 행렬을 곱합니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<unordered_map>
 
#define ll long long
#define M 1000000007
 
using namespace std;
 
int T, N, D;
 
vector<vector<int>> all(21, vector<int>(21, 0));    //모든 행렬을 곱한 행렬
unordered_map<int, vector<vector<int>>> m;        //메모제이션
 
vector<vector<int>> matrix(vector<vector<int>> arr1, vector<vector<int>> arr2)    //행렬 곱
{
    vector<vector<int>> ret(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            ll sum = 0;
            for (int k = 1; k <= N; k++) {
                sum += (((ll)arr1[i][k]%M) * ((ll)arr2[k][j]%M))%M;
                sum %= M;
            }
            ret[i][j] = sum%M;
        }
    }
 
    return ret;
}
 
vector<vector<int>> conquer(int num)        //분할 정복
{
    if (num == 1) {
        return all;
    }
    if (!m[num].empty()) {
        return m[num];
    }
 
    if (num % 2 == 0) {
        return m[num] = matrix(conquer(num / 2), conquer(num / 2));
    }
    else {
        return m[num] = matrix(conquer(num - 1), conquer(1));
    }
}
 
int main()
{
    scanf("%d %d %d", &T, &N, &D);
 
    vector<vector<int>> remain(N + 1, vector<int>(N + 1, 0));    //나머지 행렬들의 곱
    vector<vector<int>> ans(N + 1, vector<int>(N + 1, 0));        //답
 
    for (int i = 1; i <= N; i++) {    //단위 행렬로 초기화
        all[i][i] = 1;
        ans[i][i] = 1;
    }
 
    int d = D % T;    //남은 행렬들의 수
 
    for (int i = 0; i < T; i++) {
        int m, a, b, c;
        scanf("%d", &m);
        vector<vector<int>> temp(N + 1, vector<int>(N + 1, 0));
 
        for (int j = 0; j < m; j++) {
            scanf("%d %d %d", &a, &b, &c);
            temp[a][b] = c;    //i번 째 행렬
        }
        if (i == d) {    //나머지 행렬
            remain = all;
        }
        all = matrix(all, temp);
    }
 
    if (D / T != 0) {    //모든 행렬들이 곱해진 행렬이 곱해지는 횟수
        ans = conquer(D / T);
        
    }
 
    ans = matrix(ans, remain);
    
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
반응형

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

 

14942번: 개미

자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열을 이용하여 n번 이동했을 때의 노드와 거리를 저장

 

2. n번 이동했을 때 거리가 현재 가지고 있는 에너지보다 작다면 이동

 

3. 에너지가 다 닳을 때까지 이동했을 때 도착한 노드를 출력

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int n;
int energy[100001];
vector<node> list[100001];
int visited[100001];
int arr[100001][17];
int dist[100001][17];
int H;
 
void dfs(int cur)    //그래프 그리기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next.to] == 1) continue;
        arr[next.to][0] = cur;
        dist[next.to][0] = next.dist;
        dfs(next.to);
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i < H; i++) {        //순서 중요!!!
        for (int j = 2; j <= n; j++) {
            int next = arr[j][i - 1];
            if (arr[next][i - 1] == 0) continue;
            arr[j][i] = arr[next][i - 1];
            dist[j][i] = dist[next][i - 1] + dist[j][i-1];
        }
    }
}
 
int getRomm(int cur)    //최종 도달 방 찾기
{
    int ret = cur;
    int E = energy[cur];
    for (int i = H - 1; i >= 0; i--) {
        if (arr[ret][i] != 0 && dist[ret][i] <= E) {
            E -= dist[ret][i];        //순서 중요!!!
            ret = arr[ret][i];
        }
        if (ret == 1 || E == 0) break;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
    H = ceil(log2(n));
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &energy[i]);
    }
 
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    dfs(1);
 
    makeTree();
 
    for (int i = 1; i <= n; i++) {
        printf("%d\n", getRomm(i));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
반응형

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

 

13141번: Ignition

첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 것을 추천드립니다!

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

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이

rudalsd.tistory.com

 

1. 각 노드에서 노드까지 최장거리를 저장해줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 노드에서 노드까지의 최단거리를 구합니다.

 

3. 모든 노드를 체크하면서 각 노드에서 출발했을 때 가장 오래 걸리는 시간을 저장합니다.

 

4. 가장 오래 걸리는 시간들 중 가장 빠른 시간을 출력합니다.

 

위의 3번 과정에서 가장 오래 걸리는 시간을 구하는 방법은 다음과 같습니다.

 

만약 i번 노드와 j번 노드 사이의 간선들이 모두 타는 데 걸리는 시간은  두 노드 사이의 가장 긴 간선이 타는 데 걸리는 시간입니다. 따라서 노드 i와 노드 j에 모두 불이 붙은 시점에서 둘 사이에 남아 있는 노드의 길이를 구해 시간을 구해주면 됩니다.

 

먼저 시작 노드를 i라고 하고 구하고자 하는 두 노드를 각각 j, k라고 하면, 두 노드에 모두 불이 붙었을 때 남아 있는 간선의 길이는 다음과 같습니다.

 

remain = longest[ j ][ k ] - (dist[ i ][ j ] - dist[ i ][ k ])

 

불이 j노드에 도착 했을 때 남아있는 시간이 remain이므로

 

time = dist[ i ][ j ] + remain / 2

 

가 됩니다.

 

이때 remain이 0보다 작다면 모든 간선이 다 탄 상태이므로 time을 구할 필요가 없어집니다. 

 

따라서, remain > 0인 상태에서만 값을 구해주면 됩니다.

 

마지막으로 구해진 time들 중 가장 짧은 time을 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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[201][201];
int longest[201][201];
float ans = 987654321;
 
int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {        //각 노드까지 거리 초기화
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                arr[i][j] = 0;
            }
            else {
                arr[i][j] = 987654321;
            }
        }
    }
 
    for (int i = 0; i < M; i++) {
        int S, E, L;
        scanf("%d %d %d", &S, &E, &L);
 
        if (arr[S][E] > L) {    //최단거리 저장
            arr[S][E] = L;
            arr[E][S] = L;
        }
        if (longest[S][E] < L) {    //최장거리 저장
            longest[S][E] = L;
            longest[E][S] = L;
        }
    }
 
    for (int i = 1; i <= N; i++) {    //각각의 노드에서 노드까지 최단거리 갱신
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][k] > arr[j][i] + arr[i][k]) {
                    arr[j][k] = arr[j][i] + arr[i][k];
                }
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {    //i번 노드에서 시작했을 때 다 타는데 걸리는 시간 time
        float time = 0;
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                float remain = longest[j][k] - (arr[i][j] - arr[i][k]);
                if (remain > 0) {
                    time = max(time, arr[i][j] + remain / 2);
                }
            }
        }
        ans = min(time, ans);    //time 중 가장 짧은 시간 저장
    }
 
    printf("%.1f", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
반응형

1. 희소 배열(Sparse Table)

 

- 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열

- 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열

 

2. 희소 배열 만들기

 

 

보통 5번 노드에서 1번 노드까지 가기 위해서는 총 3번(5→3→6→1)의 이동이 필요합니다. 하지만 희소 배열로 이동을 한다면 총 2번의 이동이면 충분합니다. (3 = 2 + 1)

 

이처럼 간선을 1개씩 이동하지 않고, 1, 2, 4, 8... 과 같이 2^i씩 이동한다면 logn번 만에 원하는 노드에 도달할 수 있습니다.

 

이동 횟수 1번 이동 2번 이동 4번 이동
1 - - -
2 4 1 -
3 6 1 -
4 1 - -
5 3 6 -
6 1 - -
7 4 1 -
8 5 3 1
9 7 4 -
10 9 7 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
// 희소 배열
int sparseTable[n+1][logn+1];   // n은 노드의 번호를, logn은 이동 횟수를 의미
 
// 희소 배열 생성하여 이동 횟수별 도착 정점 기록
void makeSparseTable() {
    // 1번 이동해서 도착하는 정점
    for (int i=1; i<=n; i++) {
        sparseTable[i][0] = arr[i];
    }
 
    // log n번까지 이동해서 도착하는 정점
    for (int k=1; k<logn+1; k++) {
        for (int i=1; i<=n; i++) {
            int next = sparseTable[i][k-1];
            sparseTable[i][k] = sparseTable[next][k-1];
        }
    }
}
 
// v 정점에서 출발하여 n개의 간선을 이동하여 도착한 정점 찾기
int find(int n, int v) {
    for (i=size-1; i>=0; i--) {
        if ((n & (1<<i))) {
            v = sparseTable[v][i];
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.02
반응형

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

 

7578번: 공장

어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 것을 추천드립니다!

https://rudalsd.tistory.com/51?category=1073064 

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. A라인의 값들을 입력받을 때 각 숫자들의 인덱스를 저장해줍니다.

 

2. B라인의 값들을 입력 받을 때 이미 입력된 값들 중 현재 인덱스보다 더 높은 인덱스에 있는 값들의 개수를 ans에 더해줍니다.

 

3. 세그먼트 트리를 업데이트해줍니다.

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<cmath>
 
#define ll long long
 
using namespace std;
 
int N;
int A[1000001];
ll segTree[1111111];
 
ll getSum(int node, int start, int end, int sidx, int eidx)        //현재 idx값보다 큰 값들의 수를 return
{
    if (sidx > end || eidx < start) return 0;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = getSum(node * 2, start, mid, sidx, eidx);
    ll right = getSum(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
ll update(int node, int start, int end, int idx)        //현재 idx를 추가
{
    if (idx < start || idx > end) return segTree[node];
    segTree[node]++;
    if (start == end) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = update(node * 2, start, mid, idx);
    ll right = update(node * 2 + 1, mid + 1, end, idx);
 
    return segTree[node] = left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    ll ans = 0;
 
    for (int i = 1; i <= N; i++) {
        int num;
        scanf("%d", &num);
        A[num] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        int num;
        scanf("%d", &num);
        int idx = A[num];
        ans += getSum(1, 1, N, idx + 1, N);    //현재 idx보다 큰 값들의 수를 ans에 더하기
        update(1, 1, N, idx);    //현재 idx값을 넣어주기
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
반응형

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

 

16287번: Parcel

입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

모든 경우의 수를 체크하기에는 $O(N^{4})$이라는 너무 많은 시간이 걸리므로 이를 반으로 쪼개 $O(N^{2} + N^{2})$의 시간 복잡도로 문제를 풀었습니다.

 

두 물건의 무게를 인덱스 값으로 하고, dp배열에는 각 물건의 인덱스 값을 저장합니다.

 

dp[ weight ] = i

dp2[ weight ] = j

 

이때 각 물품의 무게는 모두 다르므로 특정한 weight를 만족하는 쌍은 무슨 일이 있어도 겹치지 않으므로 한 쌍만 저장해주면 됩니다.

 

그리고 다시 한번 $O(N^{2})$의 시간 복잡도로 모든 쌍을 검사하면서 인덱스가 겹치지 않는 쌍이 있다면 YES를 출력해주고, 그렇지 않다면 NO를 출력해주면 됩니다.

 

[ 소스 코드 ]

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>
 
using namespace std;
 
int w, n;
int arr[5000];
int dp[400001];
int dp2[400001];
 
 
int main()
{
    scanf("%d %d", &w, &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = arr[i] + arr[j];    //먼저 2개씩 더한 값들을 dp에 idx와 함께 저장
            if (dp[weight] == 0) {
                dp[weight] = i;
                dp2[weight] = j;
            }
        }
    }
 
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = w - arr[i] - arr[j];
            if (weight > 400000 || weight < 0) continue;    //불가능한 경우
            if (dp[weight] == i || dp2[weight] == j || dp[weight] == j || dp2[weight] == i || dp[weight] == 0) continue;    //idx가 겹치는 경우
            printf("YES");    //위의 조건이 아니라면 YES 출력
            return 0;
        }
    }
 
    printf("NO");    //불가능하다면 NO 출력
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
반응형

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

각각의 문자에 따라 구역을 0으로 바꿔주는 함수를 만들어서 적록색약이 아닌 사람이 볼 수 있는 구역의 수를 구해줍니다. 그리고 R과 G를 한 구역으로 찾는 함수를 하나 더 만들어주어서 적록색약인 사람이 볼 수 있는 구역의 수를 출력해줍니다.

 

[ 소스 코드 ]

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
 
struct node {
    int y;
    int x;
};
 
void bfs(int y, int x, char ch, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (temp[yy][xx] == ch) {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
void bfsRG(int y, int x, char temp[][101])
{
    queue<node> q;
    q.push({ y,x });
    temp[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                if (temp[yy][xx] == 'R' || temp[yy][xx] == 'G') {
                    temp[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    char arr[101][101];
    char temp[101][101];
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (temp[i][j] == 'R') {
                cnt++;
                bfs(i, j, 'R', temp);
            }
            else if (temp[i][j] == 'G') {
                cnt++;
                bfs(i, j, 'G', temp);
            }
            else if (temp[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', temp);
            }
        }
    }
 
    printf("%d ", cnt);
 
    cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'R' || arr[i][j] == 'G') {
                cnt++;
                bfsRG(i, j, arr);
            }
            else if (arr[i][j] == 'B') {
                cnt++;
                bfs(i, j, 'B', arr);
            }
        }
    }
 
    printf("%d", cnt);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
반응형

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

 

11438번: LCA 2

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정

www.acmicpc.net

 

 

[ 문제풀이 ]

 

다음 글의 두 번째 풀이 방식과 동일합니다!

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

 

[ 백준 ] 1761번 - 정점들의 거리 (C++)

https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄

rudalsd.tistory.com

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
int N, M;
vector<int> list[100001];    //간선 정보
int parent[100001][18];        //2^i번째 부모
int height[100001];            //각 노드의 높이
int visited[100001];        //방문 여부
int limit;
 
void dfs(int cur)        //그래프
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next] == 0) {
            height[next] = height[cur] + 1;
            parent[next][0] = cur;
            dfs(next);
        }
    }
}
 
int find(int a, int b)        //LCA 찾기
{
    if (height[a] > height[b]) {    //a가 루트에 더 가깝게
        int temp = a;
        a = b;
        b = temp;
    }
 
    for (int i = limit; i >= 0; i--) {    //높이 맞추기
        int mask = 1 << i;
        if (height[b] - height[a] >= mask) {
            b = parent[b][i];
        }
    }
 
    if (a == b) return a;    //같은 노드라면 a return
 
    for (int i = limit; i >= 0; i--) {        //같인 부모 찾기
        if (parent[a][i] == parent[b][i]) continue;
 
        a = parent[a][i];
        b = parent[b][i];
    }
    
    return parent[a][0];
}
 
int main()
{
    scanf("%d", &N);
 
    limit = ceil(log2(N));
 
    for (int i = 0; i < N - 1; i++) {    //간선 정보 얻기
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    dfs(1);
 
    for (int i = 1; i < limit; i++) {    //parent배열 채우기
        for (int j = 1; j <= N; j++) {
            int next = parent[j][i - 1];
            if (next != 0) {
                parent[j][i] = parent[next][i - 1];
            }
        }
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", find(a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01

+ Recent posts

티스토리툴바