반응형

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

 

2410번: 2의 멱수의 합

첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. $dp[$ $i$ $]$ 는 i의 수를 만들기 위한 경우의 수입니다.

 

2. $dp[$ $i$ $]$ 는 $dp[$ $i$ $-$ $2^{x}$ $]$ 값들에 $2^{x}$를 더한 값이므로 모든 $dp[$ $i$ $-$ $2^{x}$ $]$ 값들을 더해주면 $dp[$ $i$ $]$가 됩니다.

 

3. $dp[$ $i$ $]$ += $dp[$ $i$ $-$ $2^{x}$ $]$의 점화식을 사용하여 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
#include<iostream>
#define M 1000000000
 
using namespace std;
 
int N;
int dp[1000001];
 
int main()
{
    scanf("%d", &N);
 
    dp[0] = 1;
 
    for (int i = 0; i <= 20; i++) {
        for (int j = 1; j <= N; j++) {
            if ((j - (1 << i)) >= 0) {
                dp[j] += dp[j - (1 << i)] % M;
                dp[j] %= M;
            }
        }
    }
 
    printf("%d", dp[N]);
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9461번 - 파도반 수열 (C++)  (0) 2022.10.27
[ 백준 ] 2579번 - 계단 오르기 (C++)  (0) 2022.10.26
[ 백준 ] 2228번 - 구간 나누기 (C++)  (0) 2022.10.24
[ 백준 ] 2133번 - 타일 채우기 (C++)  (0) 2022.10.23
[ 백준 ] 5582번 - 공통 부분 문자열 (C++)  (0) 2022.10.22
반응형

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란?

 

어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 최장 증가 부분 수열(Longest Increasing Subsequence)이란 '증가하는 부분 수열' 중 가장 긴 수열을 의미합니다.

 

2. 최장 증가 부분 수열(Longest Increasing Subsequence)동작 원리

 

O(NlogN)의 시간복잡도가 걸리는 lower_bound를 활용하여 구할 수 있습니다.

 

1 2 3 5 6      

위와 같은 수열을 예로 들어서 설명드리겠습니다.

 

수열의 첫 수를 LIS에 넣어줍니다.

LIS의 마지막 수보다 현재 숫자가 더 크다면 LIS에 넣어줍니다.

그렇지 않다면 lower_bound를 활용해 현재 수보다 크거나 같은 수가 있는 곳의 index의 값을 현재 수로 바꿔줍니다.

위와 같은 방식으로 LIS를 채워주면 다음과 같은 결과를 얻을 수 있습니다.

 

유의할 점은 위의 방식으로 LIS를 구하면 길이는 구할 수 있지만 부분수열 자체는 구할 수 없습니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 뤼카의 정리 (Lucas' theorem)  (0) 2023.07.03
[ 알고리즘 ] 이분 매칭(Bipartite Matching)  (0) 2023.05.24
[ 알고리즘 ] 단절선(Articulation Bridge)  (0) 2022.08.28
[ 알고리즘 ] 단절점(Articulation Point)  (0) 2022.08.26
[ 알고리즘 ] 강한 연결 요소 추출 알고리즘(Strongly Connected Component)  (0) 2022.07.23
반응형

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

 

2228번: 구간 나누기

N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ i ][ j ] 는 i번 째 idx까지 j개의 구간으로 나누었을 때 최댓값 입니다.

 

2. 이 때 i를 포함하지 않는 dp[ i ][ j ]의 값은 DP( i - 1, j )가 됩니다.

 

3. i를 포함하는 dp[ i ][ j ]의 값은 max( dp[ i ][ j ], DP( k - 2, m - 1 ) + sum[ i ] - sum[ k - 1 ] ) 입니다.

 

4. 마지막에 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 N, M;
int arr[101];
int dp[101][51];
int sum[101];
 
int DP(int n, int m)
{
    if (n < m * 2 - 1) return -987654321;
    if (m == 0) return 0;
    if (dp[n][m] != -987654321) return dp[n][m];
 
    dp[n][m] = DP(n - 1, m);
 
    for (int i = n; i >= 1; i--) {
        int temp = DP(i - 2, m - 1);
        dp[n][m] = max(dp[n][m], temp + sum[n] - sum[i - 1]);
    }
 
    return dp[n][m];
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        sum[i] = sum[i - 1] + arr[i];
    }
 
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= (N + 1) / 2; j++) {
            dp[i][j] = -987654321;
        }
    }
 
    printf("%d", DP(N, M));
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2579번 - 계단 오르기 (C++)  (0) 2022.10.26
[ 백준 ] 2410번 - 2의 멱수의 합 (C++)  (0) 2022.10.25
[ 백준 ] 2133번 - 타일 채우기 (C++)  (0) 2022.10.23
[ 백준 ] 5582번 - 공통 부분 문자열 (C++)  (0) 2022.10.22
[ 백준 ] 2225번 - 합분해 (C++)  (0) 2022.10.21
반응형

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

 

2133번: 타일 채우기

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 점화식을 다음과 같이 세웁니다.

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

 

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

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
 
using namespace std;
 
int N;
int dp[31];
 
int main()
{
    dp[0] = 1;
    dp[2] = 3;
 
    scanf("%d", &N);
 
    for (int i = 4; i <= N; i+=2) {
        dp[i] = dp[i - 2] * 4 - dp[i - 4];
    }
 
    printf("%d", dp[N]);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2410번 - 2의 멱수의 합 (C++)  (0) 2022.10.25
[ 백준 ] 2228번 - 구간 나누기 (C++)  (0) 2022.10.24
[ 백준 ] 5582번 - 공통 부분 문자열 (C++)  (0) 2022.10.22
[ 백준 ] 2225번 - 합분해 (C++)  (0) 2022.10.21
[ 백준 ] 2011번 - 암호코드 (C++)  (0) 2022.10.20
반응형

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

 

5582번: 공통 부분 문자열

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열 str1, str2를 입력 받습니다.

 

2. str1[ i ] 와 str2[ j ]가 일치할 때 arr[ i ][ j ] = arr[ i - 1 ][ j - 1 ]  + 1의 점화식을 통해 최댓값을 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
#include<iostream>
#include<string>
 
using namespace std;
 
int arr[4001][4001];
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    string str[2];
 
    cin >> str[0] >> str[1];
 
    str[0] = '1' + str[0];
    str[1] = '1' + str[1];
 
    for (int i = 1; i < str[0].size(); i++) {
        for (int j = 1; j < str[1].size(); j++) {
            if (str[0][i] == str[1][j]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
                ans = max(ans, arr[i][j]);
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2228번 - 구간 나누기 (C++)  (0) 2022.10.24
[ 백준 ] 2133번 - 타일 채우기 (C++)  (0) 2022.10.23
[ 백준 ] 2225번 - 합분해 (C++)  (0) 2022.10.21
[ 백준 ] 2011번 - 암호코드 (C++)  (0) 2022.10.20
[ 백준 ] 2631번 - 줄세우기 (C++)  (0) 2022.10.19
반응형

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

 

2225번: 합분해

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

www.acmicpc.net

 

 

[ 문제풀이 ]


1. 점화식 dp [ i ][ j + k ] += dp [ i - 1 ][ j ]를 통해 각 위치에서의 최댓값을 저장합니다.

2. 최댓값을 1,000,000,000으로 모듈러 연산을 한 값을 dp배열에 저장합니다.

3. dp[ K ][ 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
#include<iostream>
#define M 1000000000
 
using namespace std;
 
int N, K;
int dp[201][201];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i <= N; i++) {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= K; i++) {
        for (int j = 0; j <= N; j++) {
            for (int k = 0; k <= N; k++) {
                if (j + k <= N) {
                    dp[i][j + k] += dp[i-1][j];
                    dp[i][j + k] %= M;
                }
            }
        }
    }
 
    printf("%d", dp[K][N]);
}
cs
반응형

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

[ 백준 ] 2133번 - 타일 채우기 (C++)  (0) 2022.10.23
[ 백준 ] 5582번 - 공통 부분 문자열 (C++)  (0) 2022.10.22
[ 백준 ] 2011번 - 암호코드 (C++)  (0) 2022.10.20
[ 백준 ] 2631번 - 줄세우기 (C++)  (0) 2022.10.19
[ 백준 ] 2636번 - 치즈 (C++)  (0) 2022.10.16
반응형

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

 

2011번: 암호코드

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]


1. i와 i - 1의 수를 조합하여 27이상이고 1의 자리가 0이 아닐 때 또는 10의 자리가 0이고 1의 자리가 0이 아닐 때
dp [ 1 ][ i ] = (dp [ 1 ][ i - 1 ] % M + dp [ 2 ][ i - 1 ] % M) % M;

2. 10, 20일 때
dp [ 2 ][ i ] = (dp [ 1 ][ i - 2 ] % M + dp [ 2 ][ i - 2 ] % M) % M;

3. 나머지의 경우
dp [ 1 ][ i ] = (dp [ 1 ][ i - 1 ] % M + dp [ 2 ][ i - 1 ] % M) % M;
dp [ 2 ][ i ] = (dp [ 1 ][ i - 2 ] % M + dp [ 2 ][ i - 2 ] % M) % M;

위의 점화식을 이용하여 마지막에
(dp [ 1 ][ size - 1 ] % M + dp [ 2 ][ size - 1 ] % M) % 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
#include<iostream>
#include<string>
#define M 1000000
 
using namespace std;
 
string str;
int dp[3][5001];
 
int main()
{
    cin >> str;
 
    if (str[0] == '0') {
        printf("%d", 0);
        return 0;
    }
 
    for (int i = 0; i < 2; i++) {    //초기 세팅
        if (str[i] != '0') dp[1][i] = 1;
    }
    if ((str[0] - '0') * 10 + str[1] - '0' > 0 && (str[0] - '0') * 10 + str[1] - '0' < 27) {
        dp[2][1] = 1;
    }
 
    for (int i = 2; i < str.size(); i++) {
        if (((str[i - 1] - '0') * 10 + str[i] - '0' > 26 && str[i] != '0') || (str[i-1] == '0' && str[i] > '0')) {
            dp[1][i] = (dp[1][i - 1] % M + dp[2][i - 1] % M) % M;
        } // 27이상이고 1의 자리가 0이 아닐 때 또는 10의 자리가 0이고 1의 자리가 0이 아닐 때
        else if (str[i] == '0') {
            if (str[i - 1] != '1' && str[i - 1] != '2') {    //10, 20이 아닐 때
                printf("%d", 0);
                return 0;
            }
            else {    //10, 20일 때
                dp[2][i] = (dp[1][i - 2] % M + dp[2][i - 2] % M) % M;
            }
        }
        else {    //11이상 26이하일 때
            dp[1][i] = (dp[1][i - 1] % M + dp[2][i - 1] % M) % M;
            dp[2][i] = (dp[1][i - 2] % M + dp[2][i - 2] % M) % M;
        }
    }
 
    printf("%d", (dp[1][str.size() - 1] % M + dp[2][str.size() - 1] % M) % M);
}
cs
반응형

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

[ 백준 ] 5582번 - 공통 부분 문자열 (C++)  (0) 2022.10.22
[ 백준 ] 2225번 - 합분해 (C++)  (0) 2022.10.21
[ 백준 ] 2631번 - 줄세우기 (C++)  (0) 2022.10.19
[ 백준 ] 2636번 - 치즈 (C++)  (0) 2022.10.16
[ 백준 ] 3954번 - Brainf**k 인터프리터 (C++)  (0) 2022.10.15
반응형

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

 

2631번: 줄세우기

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기

www.acmicpc.net

 

 

[ 문제풀이 ]


1. LIS를 활용하여 최장 증가 수열의 개수를 구합니다.

2. 아이들의 수에서 LIS의 사이즈를 뺀 값을 출력합니다.

 

[ 소스코드 ]

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>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[200];
vector<int> lis;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    lis.push_back(arr[0]);
 
    for (int i = 1; i < N; i++) {
        if (lis[lis.size() - 1] < arr[i]) {
            lis.push_back(arr[i]);
        }
        else {
            auto idx = lower_bound(lis.begin(), lis.end(), arr[i]);
            *idx = arr[i];
        }
    }
 
    printf("%d", N - lis.size());
}
cs
반응형

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

[ 백준 ] 2225번 - 합분해 (C++)  (0) 2022.10.21
[ 백준 ] 2011번 - 암호코드 (C++)  (0) 2022.10.20
[ 백준 ] 2636번 - 치즈 (C++)  (0) 2022.10.16
[ 백준 ] 3954번 - Brainf**k 인터프리터 (C++)  (0) 2022.10.15
[ 백준 ] 15486번 - 퇴사 2 (C++)  (0) 2022.10.14
반응형

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

 

15486번: 퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 날에 벌 수 있는 최대 금액을 저장할 dp배열을 만듭니다.

 

2. 각 날의 정보를 저장할 arr배열을 만듭니다.

 

3. for문을 통해 첫날부터 N번 째 날까지 dp [ i + t ] < dp [ i ] + p 라면 dp [ i + t ] = dp [ i ] + p를 적용시켜줍니다.

 

4. 매 날마다 최댓값을 갱신해주고, 만약 최댓값보다 낮은 금액을 번 날이 있다면 최댓값으로 갱신해줍니다.

 

5. 최댓값을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int dp[1500001];    //각 날에 벌 수 있는 최대 금액을 저장할 dp배열
pair<int, int> arr[1500001];    //각 날의 정보를 저장할 배열
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int t, p;
        scanf("%d %d", &t, &p);
        arr[i] = { t,p };
    }
 
    int Max = 0;
 
    for (int i = 0; i <= N; i++) {
        int t = arr[i].first;
        int p = arr[i].second;
        Max = max(dp[i], Max);
        if (dp[i] < Max) {
            dp[i] = Max;
        }
        if (i + t > N) continue;
        if (dp[i + t] < dp[i] + p) {
            dp[i + t] = dp[i] + p;
        }
    }
 
    printf("%d", Max);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2636번 - 치즈 (C++)  (0) 2022.10.16
[ 백준 ] 3954번 - Brainf**k 인터프리터 (C++)  (0) 2022.10.15
[ 백준 ] 14442번 - 벽 부수고 이동하기 2 (C++)  (0) 2022.10.13
[ 백준 ] 17472번 - 다리 만들기 2 (C++)  (0) 2022.10.12
[ 백준 ] 1956번 - 운동 (C++)  (0) 2022.10.11
반응형

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

 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ]의 점화식을 활용하여 각 값들을 배열에 저장하고 각 테스트 케이스마다 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
#include<iostream>
 
using namespace std;
 
struct cnt {
    int zero;
    int one;
};
 
cnt arr[41];
 
int main()
{
    arr[0] = { 1,0 };
    arr[1] = {0, 1};
    for (int i = 2; i <= 40; i++) {
        arr[i].zero = arr[i - 1].zero + arr[i - 2].zero;
        arr[i].one = arr[i - 1].one + arr[i - 2].one;
    }
    int T;
 
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N;
 
        scanf("%d", &N);
 
        printf("%d %d\n", arr[N].zero, arr[N].one);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11403번 - 경로 찾기 (C++)  (0) 2022.09.05
[ 백준 ] 17471번 - 게리맨더링 (C++)  (0) 2022.09.04
[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02
[ 백준 ] 17135번 - 캐슬 디펜스 (C++)  (0) 2022.09.01
[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31

+ Recent posts

티스토리툴바