반응형

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

 

5569번: 출근 경로

상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다.  남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[h][w][dir][turn] 배열을 만들어 해당 좌표에 해당 방향으로 방향을 바꿨는지 여부를 따져 도착할 수 있는 경우의 수를 저장합니다. (dir : 0 - 가로, 1 - 세로)

 

2. 다음과 같은 점화식을 이용하여 dp 배열을 채웁니다.

dp[ i ][ j ][ 0 ][ 0 ] = (dp[ i ][ j - 1 ][ 0 ][ 1 ] + dp[ i ][ j - 1 ][ 0 ][ 0 ]) % M;
dp[ i ][ j ][ 0 ][ 1 ] = dp[ i ][ j - 1 ][ 1 ][ 0 ] % M;
dp[ i ][ j ][ 1 ][ 0 ] = (dp[ i - 1 ][ j ][ 1 ][ 1 ] + dp[ i - 1 ][ j ][ 1 ][ 0 ]) % M;
dp[ i ][ j ][ 1 ][ 1 ] = dp[ i - 1 ][ j ][ 0 ][ 0 ] % M;

 

3. (dp[ h ][ w ][ 0 ][ 0 ] + dp[ h ][ w ][ 0 ][ 1 ] + dp[ h ][ w ][ 1 ][ 0 ] + dp[ h ][ w ][ 1 ][ 1 ]) % M 의 값을 출력합니다.

 

[ 소스코드 ]

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>
#define M 100000
 
using namespace std;
 
int dp[101][101][2][2]; // h, w, dir, turn
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int w, h;
    cin >> w >> h;
 
    for (int i = 2; i <= w; i++) {
        dp[1][i][0][0] = 1;
    }
 
    for (int i = 2; i <= h; i++) {
        dp[i][1][1][0] = 1;
    }
 
    for (int i = 2; i <= h; i++) {
        for (int j = 2; j <= w; j++) {
            dp[i][j][0][0] = (dp[i][j - 1][0][1] + dp[i][j - 1][0][0]) % M;
            dp[i][j][0][1] = dp[i][j - 1][1][0] % M;
            dp[i][j][1][0] = (dp[i - 1][j][1][1] + dp[i - 1][j][1][0]) % M;
            dp[i][j][1][1] = dp[i - 1][j][0][0] % M;
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ans += dp[h][w][i][j];
        }
    }
 
    cout << ans % M;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
반응형

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

 

13398번: 연속합 2

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 입력받고, arr 배열에 저장합니다.

 

2. 다음과 같은 점화식을 이용하여 dp 배열을 채웁니다.

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

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

 

3. 이 때, dp[ i ][ 1 ]은 해당 수를 지웠을 때의 최댓값입니다.

 

4. 모든 dp 배열의 값 중 가장 큰 값을 출력합니다. 

 

[ 소스코드 ]

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;
int arr[100000];
int dp[100000][2];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    dp[0][0] = arr[0];
 
    int ans = arr[0];
 
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]);
        dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
        ans = max(max(ans, dp[i][0]), dp[i][1]);
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
반응형

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

 

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

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. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T, N, M;
int arr[21];
int dp[21][10001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            dp[i][0] = 1;
            for (int j = 1; j <= M; j++) {
                dp[i][j] = 0;
            }
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < arr[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
                }
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
반응형

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

 

11058번: 크리보드

N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr[ N ] 배열을 선언하고, 1부터 6까지  arr[ i ] = i로 초기화해 줍니다.

 

2. 다음과 같은 점화식을 세워 값을 갱신합니다.

arr[ i ] = max( arr[ i - 3 ] * 2, arr[ i - 4 ] * 3, arr[ i - 5 ] * 4 )

 

3. arr[ N ]을 출력합니다.

 

[ 소스코드 ]

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

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

[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
반응형

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

 

2758번: 로또

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ n ][ m ] 배열을 선언하고 -1로 초기화해줍니다.

 

2. n번 째 로또 번호가 m일 때의 개수를 dp 배열에 저장합니다.

 

3. 로또 번호가 m을 넘어서면 안 되므로 m의 값을 top - down을 통해 바꿔가면서 dp의 값을 초기화합니다.

 

4. 매 테스트케이스마다 m의 값을 1부터 m까지 for문을 통해 돌면서 dfs( n, m )의 값을 모두 더해 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<cmath>
#define ll long long
 
using namespace std;
 
int T, n, m;
ll dp[11][2001];
 
ll dfs(int n, int m)
{
    if (n == 1) {
        return 1;
    }
 
    ll& ret = dp[n][m];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    for (int i = m / 2; i >= 1; i--) {
        ret += dfs(n - 1, i);
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 2000; j++) {
            dp[i][j] = -1;
        }
    }
 
    for (int t = 0; t < T; t++) {
        cin >> n >> m;
 
        ll ans = 0;
 
        for (int i = m; i >= 1; i--) {
            ans += dfs(n, i);
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
반응형

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

 

2591번: 숫자카드

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 차례로 적어 놓은 숫자를 저장하고, 점화식을 이용하여 문제를 풉니다.

 

2. 만약 str[ i ] 가 0이라면 ans[ i - 1 ] = 0, ans[ i ] = ans[ i - 2 ]의 식을 사용합니다.

 

3. 만약 str[ i - 1 ]과 str[ i ]의 숫자를 조합했을 때 34보다 작거나 같다면 ans[ i ] = ans[ i - 1 ] + ans [ i - 2 ]의 식을 사용하고, 그렇지 않다면 ans[ i ] = ans [ i - 1]의 식을 사용합니다.

 

4. ans[ str.size() - 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
#include<iostream>
#include<string>
 
using namespace std;
 
int ans[40];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string str;
 
    cin >> str;
 
    ans[0] = 1;
    if (str[1] - '0' == 0) {
        ans[1] = 1;
        ans[0] = 0;
    }
    else {
        if ((str[0] - '0') * 10 + str[1] - '0' <= 34) {
            ans[1] = 2;
        }
        else {
            ans[1] = 1;
        }
    }
 
    for (int i = 2; i < str.size(); i++) {
        if (str[i] - '0' == 0) {
            ans[i] = ans[i - 2];
            ans[i - 1] = 0;
        }
        else {
            if ((str[i - 1] - '0') * 10 + str[i] - '0' <= 34) {
                ans[i] = ans[i - 2] + ans[i - 1];
            }
            else {
                ans[i] = ans[i - 1];
            }
        }
    }
 
    cout << ans[str.size() - 1];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
반응형

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

 

3067번: Coins

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해

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. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int T;
int coin[21];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        int N, M;
        cin >> N;
        int dp[21][10001] = { 0 };
        for (int i = 1; i <= N; i++) {
            cin >> coin[i];
            dp[i][0] = 1;
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < coin[i]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i][j - coin[i]] + dp[i - 1][j];
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
[ 백준 ] 2224번 - 명제 증명 (C++)  (0) 2023.08.15
반응형

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

 

4811번: 알약

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 카탈란수를 이용하여 점화식을 세웁니다.

 

2. 이때 최대 $_{60}\textrm{C}_{60}$까지 나올 수 있으므로 comb[ i ][ j ] = comb[ i - 1 ][ j ] + comb[ i - 1 ][ j - 1 ]의 점화식을 이용하여 미리 구해줍니다.

 

3. 카탈란수의 점화식인 $\frac{1}{n+1}\binom{2n}{n}$를 이용하여 답을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
ll comb[61][61];
int N;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    comb[0][0] = 1;
    comb[1][0] = 1;
    comb[1][1] = 1;
 
    for (int i = 2; i < 61; i++) {
        for (int j = 0; j <= i; j++) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }
    }
 
    while (1) {
        cin >> N;
        if (N == 0) return 0;
 
        cout << comb[2 * N][N] / (1LL * N + 1) << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15
[ 백준 ] 2295번 - 세 수의 합 (C++)  (0) 2023.07.14
반응형

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

 

11402번: 이항 계수 4

첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

https://rudalsd.tistory.com/426

 

1.  $_{n}\textrm{C}_{r} =\,    _{n-1}\textrm{C}_{r-1} +\,  _{n-1}\textrm{C}_{r}$ 이므로 분할정복을 이용하여 $_{n}\textrm{C}_{r}$를 구해줍니다.

 

2. 뤼카의 정리를 이용하여 각각의 조합의 값들을 곱해 M으로 나눈 나머지를 출력합니다.

 

[ 소스 코드 ]

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<vector>
#define ll long long
 
using namespace std;
 
ll N, K;
int M;
ll arr[2001][2001];
 
vector<int> luca(ll N, int M)
{
    vector<int> ret;
 
    while (N) {
        int temp = N % M;
        ret.push_back(temp);
        N /= M;
    }
 
    return ret;
}
 
ll comb(int N, int R)
{
    if (N < R) return 0;
    if (R == 1) return N;
    if (R == 0) return 1;
    if (arr[N][R] != 0) return arr[N][R];
 
    return arr[N][R] = (comb(N - 1, R - 1) + comb(N - 1, R)) % M;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K >> M;
 
    vector<int> n, k;
 
    n = luca(N, M);
    k = luca(K, M);
 
    int idx = min(n.size(), k.size());
 
    ll ans = 1;
 
    for (int i = 0; i < idx; i++) {
        ans *= comb(n[i], k[i]);
        ans %= M;
        if (ans == 0) break;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01
[ 백준 ] 8981번 - 입력숫자 (C++)  (0) 2023.06.30

+ Recent posts

티스토리툴바