반응형

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
반응형

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

 

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. s = 0, e = 0으로 설정한 후, arr[ 0 ]이 홀수이면 ans = 0, cnt = 1, 그렇지 않다면 ans = 1, cnt = 0으로 초기화합니다.

 

3. s <= e && e < N일 동안 반복해주면서 cnt <= K 일 때 e++ 그렇지 않다면 s++을 해주면서 ans = max(ans, e - s + 1 - cnt)를 통해 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
#include<iostream>
 
using namespace std;
 
int N, K;
int arr[1000000];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int s, e;
    s = e = 0;
    int cnt = 0;
    int ans = 1;
 
    if (arr[0] % 2 == 1) {
        cnt = 1;
        ans = 0;
    }
 
    while (s <= e && e < N) {
 
        if (cnt <= K || s == e) {
            e++;
            if (arr[e] % 2 == 1) cnt++;
        }
        else {
            if (arr[s] % 2 == 1)cnt--;
            s++;
        }
 
        if (e < N) {
            ans = max(ans, e - s + 1 - cnt);
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20366번 - 같이 눈사람 만들래? (C++)  (0) 2023.04.11
[ 백준 ] 13144번 - List of Unique Numbers (C++)  (0) 2023.04.10
[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07
[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
반응형

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
반응형

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

 

17400번: 깃발춤

첫 번째 줄에는 깃발춤을 진행하는 공연자의 명수인 자연수 N과 상황 변화의 개수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 300,000, 1 ≤ Q ≤ 300,000) 두 번째 줄에는 정수 c1, c2, ..., cN

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 번갈아가면서 춤을 추므로 segmentTree[ node ].first에는 idx % 2 == 0인 값을 second에는 idx % 2 == 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
 
int N, Q;
int arr[300001];
pair<ll, ll> segTree[1050000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        if (s % 2 == 0) {
            segTree[node].first = arr[s];
        }
        else {
            segTree[node].second = arr[s];
        }
        return;
    }
 
    int m = (s + e) / 2;
 
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].first = segTree[node * 2].first + segTree[node * 2 + 1].first;
    segTree[node].second = segTree[node * 2].second + segTree[node * 2 + 1].second;
}
 
pair<ll,ll> getTree(int node, int s, int e, int sidx, int eidx)
{
    if (eidx < s || e < sidx) return { 0,0 };
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
 
    pair<ll, ll> left = getTree(node * 2, s, m, sidx, eidx);
    pair<ll, ll> right = getTree(node * 2 + 1, m+1, e, sidx, eidx);
    
    return { left.first + right.first, left.second + right.second };
}
 
void updateTree(int node, int s, int e, int idx, int x)
{
    if (s > idx || e < idx) return;
    if (idx % 2 == 0) {
        segTree[node].first += x;
    }
    else {
        segTree[node].second += x;
    }
 
    if (s != e) {
        int m = (s + e) / 2;
 
        updateTree(node * 2, s, m, idx, x);
        updateTree(node * 2 + 1, m + 1, e, idx, x);
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        int com, L, R;
        scanf("%d %d %d", &com, &L, &R);
 
        if (com == 1) {
            pair<ll, ll> temp = getTree(1, 1, N, L, R);
            printf("%lld\n", abs(temp.first - temp.second));
        }
        else {
            updateTree(1, 1, N, L, R);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (C++)  (0) 2023.04.09
[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
반응형

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

 

1306번: 달려라 홍준

첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 각각의 노드에 해당 범위의 최댓값을 저장하고, for문을 통해 인덱스를 슬라이싱 하면서 원하는 범위에서의 최댓값을 출력합니다.

 

[ 소스코드 ]

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<cmath>
 
using namespace std;
 
int N, M;
int segTree[2111111];
int arr[1000001];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = max(segTree[node * 2], segTree[node * 2 + 1]);
}
 
int getTree(int node, int s, int e, int sidx, int eidx)
{
    if (eidx < s || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    int left = getTree(node * 2, s, m, sidx, eidx);
    int right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return max(left, right);
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = M; i <= N - M + 1; i++) {
        printf("%d\n", getTree(1, 1, N, i - (M - 1), i + M - 1));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2230번 - 수 고르기 (C++)  (0) 2023.04.08
[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07
[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
반응형

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

 

17845번: 수강 과목

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다.  이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

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

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

[ 백준 ] 17400번 - 깃발춤 (C++)  (0) 2023.04.07
[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
반응형

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

 

1321번: 군인

첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cmath>
 
using namespace std;
 
int N, M;
int segTree[1111111];
int arr[500001];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void updateTree(int node, int s, int e, int idx, int a)
{
    if (idx < s || e < idx) return;
    segTree[node] += a;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx, a);
        updateTree(node * 2 + 1, m + 1, e, idx, a);
    }
}
 
void getTree(int node, int s, int e, int idx)
{
    if (s == e) {
        printf("%d\n", s);
        return;
    }
 
    int m = (s + e) / 2;
    int left = segTree[node * 2];
    
    if (left >= idx) {
        getTree(node * 2, s, m, idx);
    }
    else {
        getTree(node * 2 + 1, m + 1, e, idx - left);
    }
 
    return;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int com, idx;
        scanf("%d %d", &com, &idx);
        if (com == 1) {
            int a;
            scanf("%d", &a);
            arr[idx] += a;
            updateTree(1, 1, N, idx, a);
        }
        else {
            getTree(1, 1, N, idx);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1306번 - 달려라 홍준 (C++)  (0) 2023.04.06
[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
반응형

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

 

14728번: 벼락치기

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

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
#include<iostream>
 
using namespace std;
 
int N, T;
pair<int, int> arr[101];
int ans[101][10001];
 
int main()
{
    scanf("%d %d", &N, &T);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 1; i <= N; i++) {
        int cost = arr[i].first;
        int point = arr[i].second;
 
        for (int j = 1; j <= T; j++) {
            if (j < cost) {
                ans[i][j] = ans[i - 1][j];
            }
            else {
                ans[i][j] = max(ans[i - 1][j], ans[i - 1][j - cost] + point);
            }
        }
    }
 
    printf("%d", ans[N][T]);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17845번 - 수강 과목 (C++)  (0) 2023.04.05
[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
반응형

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

 

13424번: 비밀 모임

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. arr[ N ][ N ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 줍니다.

 

3. 1부터 N까지 K개의 방에서부터 i까지의 거리를 모두 더해주고, 그 값들 중 가장 작은 값을 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
58
59
60
61
62
63
64
#include<iostream>
 
using namespace std;
 
int arr[101][101];
int room[101];
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N, M, K;
        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 a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            arr[a][b] = c;
            arr[b][a] = c;
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
 
        scanf("%d", &K);
        int dist = 987654321;
        int ans = 0;
 
        for (int i = 0; i < K; i++) {
            scanf("%d", &room[i]);
        }
 
        for (int i = 1; i <= N; i++) {
            int temp = 0;
            for (int j = 0; j < K; j++) {
                temp += arr[i][room[j]];
            }
            if (dist > temp) {
                dist = temp;
                ans = i;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1321번 - 군인 (C++)  (0) 2023.04.04
[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
반응형

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

 

1719번: 택배

첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

 

1. arr[ n ][ n ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.

 

2. ans[ n ][ n ] 배열을 만들어 각 노드까지 갈 때 가장 처음으로 거치는 노드를 저장해 줍니다.

 

3. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 주고, 최단거리를 갱신할 때 ans[ j ][ k ] = ans[ j ][ i ]를 같이 처리해 줍니다.

 

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
#include<iostream>
 
using namespace std;
 
int n, m;
int arr[201][201];
int ans[201][201];
 
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] = 987654321;
            }
        }
    }
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        ans[a][b] = b;
        ans[b][a] = a;
        arr[a][b] = c;
        arr[b][a] = c;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (arr[j][i] != 0 && arr[i][k] != 0) {
                    if (arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                        ans[j][k] = ans[j][i];
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                printf("- ");
            }
            else {
                printf("%d ", ans[i][j]);
            }
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14728번 - 벼락치기 (C++)  (0) 2023.04.03
[ 백준 ] 13424번 - 비밀 모임 (C++)  (0) 2023.04.02
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 17490번 - 일감호에 다리 놓기 (C++)  (0) 2023.03.30
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29

+ Recent posts

티스토리툴바