반응형

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

 

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제는 간단한 점화식을 세워서 풀 수 있었습니다.

 

dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] * 2

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
 
using namespace std;
 
int n;
int dp[1001];
 
int main()
{
    cin >> n;
 
    dp[1] = 1;
    dp[2] = 3;
 
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] * 2;
        dp[i] %= 10007;
    }
 
    cout << dp[n];
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
[ 백준 ] 3190번 - 뱀 (C++)  (0) 2022.08.15
[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
반응형

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

 

2618번: 경찰차

첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

재귀 함수와 다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

 

먼저 dp[dp [ 1001 ][ 1001 ] 배열을 만듭니다. dp [ a ][ b ]에서 a는 1번 자동차의 위치, b는 2번 자동차의 위치입니다. 더 정확하게는 a번째 사건의 위치가 현재 1번 자동차의 위치, b번째 사건의 위치가 현재 2번 자동차의 위치입니다.

 

dist1은 현재 1번 자동차의 위치에서 다음 사건 위치로 옮길 때의 거리, dist2는 현재 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<cmath>
 
using namespace std;
 
struct acc {        //사고의 위치 struct
    int y;
    int x;
};
 
int N, W;
 
acc arr[1001];        //사고의 위치를 저장할 배열
int dp[1001][1001];    //dp[a][b] a는 1번 자동차, b는 2번 자동차의 현재 사건 위치
 
int dist(acc a, acc b)        //a점과 b점의 거리 return
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}
 
int dfs(int a, int b)
{
    if (a == W || b == W) return 0;    //마지막 사건이라면
    if (dp[a][b] != 0) return dp[a][b];    //한번이라도 저장되었다면
 
    int nAcc = max(a, b) + 1;    //다음 사고 번호
    int dist1, dist2;
 
    if (a == 0) {        //1번 자동차가 움직였을 때의 거리
        dist1 = dist(arr[nAcc], { 1,1 });
    }
    else {
        dist1 = dist(arr[nAcc], arr[a]);
    }
    if (b == 0) {        //2번 자동차가 움직였을 때의 거리
        dist2 = dist(arr[nAcc], { N,N });
    }
    else {
        dist2 = dist(arr[nAcc], arr[b]);
    }
 
    return dp[a][b] = min(dist1 + dfs(nAcc, b), dist2 + dfs(a, nAcc));
}
 
void route(int a, int b)
{
    if (a == W || b == W) return;
 
    int nAcc = max(a, b) + 1;
    int dist1, dist2;
 
    if (a == 0) {
        dist1 = dist(arr[nAcc], { 1,1 });
    }
    else {
        dist1 = dist(arr[nAcc], arr[a]);
    }
    if (b == 0) {
        dist2 = dist(arr[nAcc], { N,N });
    }
    else {
        dist2 = dist(arr[nAcc], arr[b]);
    }
 
    if (dp[nAcc][b] + dist1 < dp[a][nAcc] + dist2) {
        printf("1\n");        //1번 자동차가 움직이는 게 가장 짧은 거리일 때
        route(nAcc, b);
    }
    else {                    //2번 자동차가 움직이는 게 가장 짧은 거리일 때
        printf("2\n");
        route(a, nAcc);
    }
 
}
 
int main()
{
    cin >> N >> W;
 
    for (int i = 1; i <= W; i++) {
        scanf("%d %d", &arr[i].y, &arr[i].x);
    }
 
    printf("%d\n", dfs(0, 0));
    route(0, 0);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2243번 - 사탕상자 (C++)  (0) 2022.07.29
[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27
[ 백준 ] 14938번 - 서강그라운드 (C++)  (0) 2022.07.25
[ 백준 ] 2150번 - Strongly Connected Component (C++)  (0) 2022.07.24
[ 백준 ] 1948번 - 임계경로 (C++)  (0) 2022.07.22
반응형

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

 

1086번: 박성원

첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

모든 조합에 대해 문제를 푼다면 O(15!)이므로 2초 안에 풀 수 없습니다. 따라서 비트 마스킹을 통해 중복으로 쓰이는 순열들을 저장해서 씀으로써 시간을 줄일 수 있습니다.

 

또한 $123456$의 나머지를 구할 때는 (123*1000) + 456 이므로 ( ( 123 % K ) * ( 1000 % K ) ) % K + 456 % K로 구해주시면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<string>
#include<cstring>
 
#define ll long long
 
using namespace std;
 
int N, K;
string arr[16];
ll dp[1 << 15][100];
int mods[15];
int digit[51];
 
ll GCD(ll a, ll b)        //최대 공약수 구하기
{
    while (a != 0) {
        ll temp = b % a;
        b = a;
        a = temp;
    }
 
    return b;
}
 
int mod(string num)        //입력된 숫자를 K로 나눈 나머지 구하기
{
    int ret = 0;
 
    for (int i = 0; i < num.size(); i++) {
        ret = (ret * 10) % K + (num[i] - '0') % K;
        ret %= K;
    }
 
    return ret;
}
 
ll Fac(int num)        //팩토리얼
{
    ll ret = 1;
 
    for (int i = 1; i <= num; i++) {
        ret *= i;
    }
 
    return ret;
}
 
ll DP(int cur, int mod)        //나머지별로 개수 저장
{
    if (cur == (1 << N) - 1) {    //모든 수를 썼는가?
        if (mod == 0) return 1;
        else return 0;
    }
 
    ll& ret = dp[cur][mod];
 
    if (ret != -1) return dp[cur][mod];    //사용된 적이 있는가?
        
    ret = 0;
 
    for (int i = 0; i < N; i++) {
        int mask = 1 << i;
 
        if (cur & mask) continue;        //이미 사용된 숫자면 continue
 
        ret += DP(cur | mask, ((mod * digit[arr[i].size()]) % K + mods[i]) % K);
    }
 
    return ret;
}
 
int main()
{
    memset(dp, -1, sizeof(dp));
    digit[0] = 1;
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    cin >> K;
 
    for (int i = 0; i < N; i++) {
        mods[i] = mod(arr[i]);
    }
 
    for (int i = 1; i <= 50; i++) {
        digit[i] = ((digit[i - 1] % K) * (10 % K)) % K;
    }
 
    ll numerator = DP(0, 0);    //분자
    ll denominator = Fac(N);    //분모
    if (numerator == 0) {
        cout << "0/1";
        return 0;
    }
 
    if (numerator == denominator) {
        cout << "1/1";
        return 0;
    }
    
    ll gcd = GCD(numerator, denominator);
 
    cout << numerator / gcd << "/" << denominator / gcd;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1761번 - 정점들의 거리 (C++)  (0) 2022.07.18
[ 백준 ] 1708번 - 볼록 껍질 (C++)  (0) 2022.07.17
[ 백준 ] 17371번 - 이사 (C++)  (0) 2022.07.14
[ 백준 ] 14428번 - 수열과 쿼리 16 (C++)  (0) 2022.07.13
[ 백준 ] 13977번 - 이항 계수와 쿼리 (C++)  (0) 2022.07.12
반응형

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

 

2096번: 내려가기

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

매우 간단한 dp문제였습니다. 하지만 메모리 제한이 4MB였기 때문에 배열에 모든 값을 받고 메모제이션을 진행하게 된다면 메모리 초과가 납니다. 따라서, 수를 입력받을 때마다 값을 처리해줄 필요가 있었습니다.

 

이전에 메모제이션 한 값들과 현재 입력받은 값을 연산하고 tempMax, tempMin 에 저장해 준 후 마지막에 Max, Min에 다시 저장해주는 방법을 통해 문제를 풀었습니다.

 

[ 소스 코드 ]

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 N;
int Max[3];
int Min[3];
int tempMax[3];
int tempMin[3];
int dx[3] = { -1,0,1 };
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int a, b, c;
 
        scanf("%d %d %d", &a, &b, &c);
 
        tempMax[0] = max(Max[0], Max[1]) + a;
        tempMax[1] = max(Max[0], max(Max[1], Max[2])) + b;
        tempMax[2] = max(Max[1], Max[2]) + c;
        tempMin[0] = min(Min[0], Min[1]) + a;
        tempMin[1] = min(Min[0], min(Min[1], Min[2])) + b;
        tempMin[2] = min(Min[1], Min[2]) + c;
        for (int j = 0; j < 3; j++) {
            Max[j] = tempMax[j];
            Min[j] = tempMin[j];
        }
    }
 
    cout << max(Max[0], max(Max[1], Max[2])) << " " << min(Min[0], min(Min[1], Min[2]));
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3015번 - 오아시스 재결합 (C++)  (0) 2022.07.10
[ 백준 ] 11505번 - 구간 곱 구하기 (C++)  (0) 2022.07.09
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07
[ 백준 ] 14502번 - 연구소 (C++)  (0) 2022.07.06
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
반응형

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

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

 

2098번: 외판원 순회

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

[ 알고리즘 ] 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)

오늘 설명할 알고리즘은 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)입니다. 조합 최적화 문제로 전산학에서 연구된 가장 유명한 문제 중 하나입니다. 이 문제의 요구사항은 간단합니다.

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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int N;
int arr[16][16];
int dp[16][(1<<16)];
int visitedAll;
 
int dfs(int node, int via)
{
    if (via == visitedAll) {
        if (arr[node][0] == 0) return 987654321;
        return arr[node][0];
    }
 
    if (dp[node][via] != -1) return dp[node][via];    //방문한 적 있다면 dp[vode][via]출력
    dp[node][via] = 987654321;            //아닐경우
 
    for (int i = 0; i < N; i++) {
        if (via & (1 << i)) continue;    //이미 방문
        if (arr[node][i] == 0) continue;    //길이 없다면
        dp[node][via] = min(dp[node][via], arr[node][i] + dfs(i, via | (1 << i)));
    }
    return dp[node][via];
}
 
int main()
{
    cin >> N;
 
    visitedAll = (1 << N) - 1;
    memset(dp, -1, sizeof(dp));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    int ans = dfs(0, 1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19

+ Recent posts

티스토리툴바