반응형

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

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

 

1562번: 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

[ 백준 ] 10844번 - 쉬운 계단 수 (C++)

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [ 문제풀이 ] 항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을..

rudalsd.tistory.com

위의 문제와 많이 유사하지만 0~9까지의 모든 숫자가 들어가야 하므로 조금 더 까다로운 문제입니다.

 

위의 일반적인 계단 수를 구하는 문제를 풀어보시고 오는 것을 추천드립니다!!

 

쉬운 계단 수 문제와 유사하지만 한가지 개념만 더한다면 쉽게 풀 수 있는 문제입니다.

 

0~9까지의 모든 숫자가 들어가 있는 계단수는 0과 9에 모두 맞닿아있어야 합니다. 따라서 0에 맞닿아있으면 1번 비트에 저장하고, 9에 맞닿아있으면 2번 비트에 저장하고, 0과 9에 모두 닿아있으면 3번 비트에 저장합니다.

 

dp배열에 저장해 나가면 결국 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
#include <iostream>
 
using namespace std;
 
int N;
long long dp[10][101][4];                //각 숫자가 들어갈 수 있는 개수를 저장할 배열
                                        //1 : 0과 닿음, 2 : 9와 닿음, 3 : 0, 9와 닿음
int main()
{
    cin >> N;
 
    long long cnt = 0;                    //총 개수를 저장할 변수
 
    for (int i = 1; i < 9; i++) {        //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로
        dp[i][1][0] = 1;                //모두 1로 경신
    }
 
    dp[9][1][2] = 1;
 
    for (int i = 2; i <= N; i++) {        //2자릿수 부터 돌면서
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 4; k++) {
                if (j == 0) {            //0과 닿아있으면 k|1에 그 전의 모든 값들을 더함
                    dp[j][i][k | 1] += dp[1][i - 1][k];
                    dp[j][i][k | 1] %= 1000000000;
                }
                else if (j == 9) {        //9와 닿아있으면 k|2에 그 전의 모든 값들을 더함
                    dp[j][i][k | 2] += dp[8][i - 1][k];
                    dp[j][i][k | 2] %= 1000000000;
                }
                else {                    //아니라면 전의 값들 중 계단수들의 값들을 더함
                    dp[j][i][k] = dp[j - 1][i - 1][k] + dp[j + 1][i - 1][k];
                    dp[j][i][k] %= 1000000000;
                }
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        cnt += dp[i][N][3];
        cnt %= 1000000000;
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26

+ Recent posts

티스토리툴바