반응형

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

 

11578번: 팀원 모집

3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 1부터 $2^M$ - 1까지 for문을 이용해 돌면서 해당 비트가 1이라면 해당 팀원이 풀 수 있는 문제들을 풀고, cnt++를 해준 후 모든 문제를 풀었다면 가장 낮은 cnt를 ans에 저장해 줍니다.

 

2. ans가 갱신되지 않았다면 -1을 출력하고 그렇지 않다면 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<vector>
#include<cmath>
 
using namespace std;
 
int N, M;
vector<int> list[11];
int ans = 987654321;
int mask;
 
void check(int num)
{
    int tmp = 0;
    int cnt = 0;
    for (int i = 0; i < M; i++) {
        if (num & 1 << i) {
            for (auto& next : list[i]) {
                tmp |= 1 << next;
            }
            cnt++;
        }
    }
 
    if (tmp == mask) {
        ans = min(ans, cnt);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int n;
        cin >> n;
 
        for (int j = 0; j < n; j++) {
            int tmp;
            cin >> tmp;
            list[i].push_back(tmp);
        }
    }
 
    mask = pow(2, N + 1) - 2;
    
    for (int i = 1; i < pow(2, M); i++) {
        check(i);
    }
 
    if (ans == 987654321) cout << -1;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
반응형

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

 

15243번: Tiling

Domino tiles (or dominoes) are rectangular pieces of size 2x1. Each square contains a number from 1 to 6. These pieces are used to play a game but in this problem we are going to use them for something different. We can build rectangles of certain width W

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 타일을 배치할 총너비가 홀수라면 배치할 방법이 없으므로 0을 출력해 줍니다.

 

2. 너비가 짝수라면 다음과 같은 점화식을 사용하여 문제를 풀어줍니다.

arr[ i ] = arr[ i - 2 ] * 4 - arr[ i - 4 ]

 

3. 수가 int 범위를 넘어갈 수 있으므로 long long 자료형을 쓰고, 1000000007을 Modulo를 통해 답을 출력합니다.

 

[ 소스코드 ]

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>
#define ll long long
#define M 1000000007
using namespace std;
 
ll arr[1001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int W;
    cin >> W;
 
    arr[0] = 1;
    arr[2] = 3;
 
    if (W % 2 == 0) {
        for (int i = 4; i <= W; i += 2) {
            arr[i] = ((arr[i - 2] % M) * 4) % M - arr[i - 4] % M + M;
            arr[i] %= M;
        }
    }
    else {
        cout << 0;
        return 0;
    }
 
    cout << arr[W];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15
반응형

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

 

2830번: 행성 X3

상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. cnt 배열을 만들어 입력받는 모든 숫자의 2진수 자릿수 별 1의 개수를 저장합니다.

 

2. XOR을 할 경우 서로 다를 때 1이 되므로 (1 << i) * 0의 개수*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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
int cnt[20];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
 
        int bi = 0;
 
        while (num != 0) {
            cnt[bi] += (num & 1);
            num >>= 1;
            bi++;
        }
    }
 
    ll ans = 0;
 
    for (int i = 0; i < 20; i++) {
        ans += (1LL << i) * 1LL * cnt[i] * (1LL * N - cnt[i]);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 17071번 - 숨바꼭질 5 (C++)  (0) 2023.06.21
[ 백준 ] 5022번 - 연결 (C++)  (1) 2023.06.19
[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18
[ 백준 ] 2164번 - 카드2 (C++)  (0) 2023.06.17
반응형

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

 

1175번: 배달

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ N ][ M ][ dir ][ del ] 배열을 만들어서 위치, 방향, 배달 여부를 저장합니다.

 

2. 지도에서 S의 위치를 queue에 넣고, '.'로 초기화합니다.

 

3. 지도에서 C의 위치를 '0', '1'로 초기화합니다.

 

4. bfs를 통해 배달을 하고, 숫자를 만나면 del | (1 << arr [ yy ][ xx ] - '0')를 통해 배달 여부를 초기화합니다.

 

5. 배달을 완료했을 때 cnt를 출력합니다.

 

6. 배달이 불가능할 때 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int visited[50][50][4][4];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
char arr[51][51];
 
struct node {
    int y;
    int x;
    int dir;
    int del;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
    queue<node> q;
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 'S') {
                q.push({ i,j,-1,0,0 });
                visited[i][j][0][0] = 1;
                visited[i][j][1][0] = 1;
                visited[i][j][2][0] = 1;
                visited[i][j][3][0] = 1;
                arr[i][j] = '.';
            }
            if (arr[i][j] == 'C') {
                arr[i][j] = '0' + cnt++;
            }
        }
    }
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int dir = q.front().dir;
        const int del = q.front().del;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (del == 3) {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            if (i != dir) {
                const int yy = y + dy[i];
                const int xx = x + dx[i];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                    if (arr[yy][xx] == '.' && visited[yy][xx][i][del] == 0) {
                        visited[yy][xx][i][del] = 1;
                        q.push({ yy,xx,i,del,cnt + 1 });
                    }
                    else if (arr[yy][xx] >= '0' && arr[yy][xx] < '2') {
                        const int temp = del | (1 << arr[yy][xx] - '0');
                        if (visited[yy][xx][i][temp] == 0) {
                            visited[yy][xx][i][temp] = 1;
                            q.push({ yy,xx,i,temp,cnt + 1});
                        }
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 17090번 - 미로 탈출하기 (C++)  (0) 2023.01.27
반응형

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

 

17244번: 아맞다우산

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력을 받고, X를 만날 때마다 ea변수를 1씩 늘려주고, X를 ea의 값으로 바꿔줍니다.

 

2. visited [ ea ][ y ][ x ] 배열을 만들어 주운 물건을 비트마스킹을 통해 체크하고, 방문 여부를 체크합니다. 이때, ea의 최댓값은 $2^{5}$(=32)입니다.

 

3. 물건을 주울 때마다 stf 변수에 현재 물건의 번호를 통해 추가해줍니다.

 

4. 모든 물건을 다 줍고, 도착점에 도착하면 cnt를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[51][51];
int Sy, Sx;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[32][51][51];
 
struct node {
    int y;
    int x;
    int cnt;
    int stf;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%s", &arr[i]);
    }
 
    int ea = 0;
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'S') {
                Sy = i;
                Sx = j;
            }
            else if (arr[i][j] == 'X') {
                arr[i][j] = '0' + ea;
                ea++;
            }
        }
    }
 
    queue<node> q;
 
    q.push({ Sy,Sx,0,0 });
    visited[0][Sy][Sx] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int cnt = q.front().cnt;
        const int stf = q.front().stf;
        q.pop();
 
        if (arr[y][x] == 'E') {
            if (stf == (1 << ea) - 1) {
                printf("%d", cnt);
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < M && xx >= 0 && xx < N) {
                if (arr[yy][xx] >='0' && arr[yy][xx] <'5') {
                    const int temp = stf | (1 << (arr[yy][xx] - '0'));
                    if (visited[temp][yy][xx] != 1) {
                        visited[temp][yy][xx] = 1;
                        q.push({ yy,xx,cnt + 1,temp });
                    }
                }
                else if (arr[yy][xx] != '#') {
                    if (visited[stf][yy][xx] != 1) {
                        visited[stf][yy][xx] = 1;
                        q.push({ yy,xx,cnt + 1,stf });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28
반응형

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

 

1194번: 달이 차오른다, 가자.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 민식이의 이동을 기록할 visited [ key ][ y ][ x ] 배열을 만듭니다. 여기서 key의 최댓값은 a~f까지 총 6개이므로 $2^{6}$(=128)입니다.

 

2. bfs를 통해 이동을 하다가 a~f사이 알파벳을 만나면 현재 key에 1 << arr [ y ][ x ] - 'a'의 값을 추가해 줍니다.

 

3. 이동 중 A~F사이 알파벳을 만나면 현재 key에 1 << arr [ y ][ x ] - 'A'의 값이 존재하면 queue에 넣고, 존재하지 않는다면 넘어갑니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[51][51];
int visited[130][50][50];
int Sy, Sx;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int key;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == '0') {
                arr[i][j] = '.';
                Sy = i;
                Sx = j;
            }
        }
    }
 
    queue<node> q;
    q.push({ Sy,Sx,0,0 });
    visited[0][Sy][Sx] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int key = q.front().key;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (arr[y][x] == '1') {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '.' || arr[yy][xx] == '1') {
                    if (visited[key][yy][xx] != 1) {
                        visited[key][yy][xx] = 1;
                        q.push({ yy,xx,key,cnt + 1 });
                    }
                }
                else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'f') {
                    int newKey = key | (1 << arr[yy][xx] - 'a');
                    if (visited[newKey][yy][xx] != 1) {
                        visited[newKey][yy][xx] = 1;
                        q.push({ yy,xx,newKey,cnt + 1 });
                    }
                }
                else if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'F') {
                    if (1 << (arr[yy][xx] - 'A') & key) {
                        if (visited[key][yy][xx] != 1) {
                            visited[key][yy][xx] = 1;
                            q.push({ yy,xx,key,cnt + 1 });
                        }
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 2589번 - 보물섬 (C++)  (0) 2022.12.27
[ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++)  (0) 2022.12.26
[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25
반응형

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

 

17182번: 우주 탐사선

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/24

 

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

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

rudalsd.tistory.com

 

1. 플로이드 와샬 알고리즘을 바탕으로 각각의 노드에서 노드까지의 최단 거리를 저장합니다.

 

2. 재귀 함수를 통해 모든 도시를 방문했을 때 최단 거리를 ans에 저장합니다.

 

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
 
using namespace std;
 
int N, K;
int arr[10][10];
int dist[10][10];
int visited[10];
int ans = 987654321;
int hap;
 
void dfs(int cur, int level)
{
    if (level == N - 1) {
        ans = min(ans, hap);
        return;
    }
 
    for (int i = 0; i < N; i++) {
        if (visited[i] != 1) {
            visited[i] = 1;
            hap += dist[cur][i];
            dfs(i, level + 1);
            hap -= dist[cur][i];
            visited[i] = 0;
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            dist[i][j] = arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
 
    visited[K] = 1;
 
    dfs(K, 0);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
[ 백준 ] 2550번 - 전구 (C++)  (0) 2022.11.28
[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
반응형

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

 

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

크기가 20인 배열을 만들어 각 수의 존재를 기록하고 check명령 시 index로 접근해 존재 유무를 판단해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int M;
int arr[21];
 
int main()
{
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        char input[10] = { 0 };
        int num;
        scanf("%s", input);
 
        if (!strcmp(input, "add")) {
            scanf("%d", &num);
            arr[num] = 1;
        }
        else if (!strcmp(input, "remove")) {
            scanf("%d", &num);
            arr[num] = 0;
        }
        else if (!strcmp(input, "check")) {
            scanf("%d", &num);
            printf("%d\n", arr[num]);
        }
        else if (!strcmp(input, "toggle")) {
            scanf("%d", &num);
            if (arr[num] == 1) arr[num] = 0;
            else arr[num] = 1;
        }
        else if (!strcmp(input, "all")) {
            for (int i = 1; i <= 20; i++) {
                arr[i] = 1;
            }
        }
        else {
            for (int i = 1; i <= 20; i++) {
                arr[i] = 0;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1107번 - 리모컨 (C++)  (0) 2022.09.20
[ 백준 ] 1012번 - 유기농 배추 (C++)  (0) 2022.09.19
[ 백준 ] 21610번 - 마법사 상어와 비바라기 (C++)  (0) 2022.09.17
[ 백준 ] 17779번 - 게리맨더링 2 (C++)  (0) 2022.09.16
[ 백준 ] 5373번 - 큐빙 (C++)  (0) 2022.09.15
반응형

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

 

14939번: 불 끄기

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

처음엔 dfs를 활용해서 풀었으나 100%에서 계속 틀렸습니다가 떠서 비트 마스킹으로 풀었습니다.

 

첫 줄의 스위치를 누르는 모든 경우의 수를 구한 후 arr [ i - 1][ j ]의 전구가 켜져 있다면 arr [ i ][ j ]의 스위치를 눌러서 끄고, 마지막에 마지막 줄에 전구가 다 꺼져있다면 불을 끌 수 있는 경우이므로 이때의 cnt를 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
 
using namespace std;
 
char arr[10][10];
char temp[10][10];
int dy[5] = { -1,1,0,0,0 };
int dx[5] = { 0,0,0,-1,1 };
int cnt;
int ans = 999;
 
void turn(int y, int x)        //스위치를 누르면 상태 변경
{
    for (int i = 0; i < 5; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy >= 0 && yy < 10 && xx >= 0 && xx < 10) {
            if (temp[yy][xx] == 'O') {
                temp[yy][xx] = '#';
            }
            else {
                temp[yy][xx] = 'O';
            }
        }
    }
}
 
int check()        //전구를 다 끌 수 있는지 체크 후 0 또는 1 return
{
    for (int i = 1; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (temp[i - 1][j] == 'O') {
                turn(i, j);
                cnt++;
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        if (temp[9][i] == 'O') {
            return 0;
        }
    }
 
    return 1;
}
 
 
//void dfs(int level)
//{
//    if (level == 10) {
//        int ch = check(cnt);
//        if (ch) {
//            ans = min(ans, ch);
//        }
//        return;
//    }
//
//    for (int i = 0; i < 2; i++) {
//        if (i == 0) {
//            turn(0, level, arr);
//            cnt++;
//            dfs(level + 1);
//            turn(0, level, arr);
//            cnt--;
//        }
//        else {
//            dfs(level + 1);
//        }
//    }
//}
 
int main()
{
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int t = 0; t < 1024; t++) {        //모든 경우의 수
        cnt = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        for (int i = 0; i < 10; i++) {
            if (t & (1 << i)) {
                turn(0, i);
                cnt++;
            }
        }
 
        if (!check()) continue;        //check()가 0이면 continue
 
        ans = min(ans, cnt);
    }
 
    if (ans == 999) {
        cout << -1;
    }
    else {
        cout << ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21

+ Recent posts

티스토리툴바