반응형

www.acmicpc.net/problem/13398

 

13398번: 연속합 2

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

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int n, ans, arr[100001], dp[2][100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> arr[i];
    ans = dp[0][0] = dp[1][0] = arr[0];
    /*
        dp[0][i]: 원소 제거 안한 연속합
        dp[1][i]: 원소 제거 한 연속합
          1) i번째 제거 -> 1 ~ i-1 제거하면 안됨 (dp[0][i-1])
          2) i번째 포함 -> 1 ~ i-1 중 하나 제거해야 함 (arr[i] + dp[1][i-1])
    */
    for (int i = 1;i < n;i++) {
        dp[0][i] = arr[i] + max(0, dp[0][i-1]);
        dp[1][i] = max(dp[0][i-1], dp[1][i-1] + arr[i]);
        ans = max(ans, max(dp[0][i], dp[1][i]));
    }
    cout << ans;
}
cs
반응형

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

백준 1103  (0) 2021.07.08
백준 11054  (0) 2021.02.19
백준 2133 [복습 필수] (점화식)  (0) 2021.02.17
백준 11055  (0) 2021.02.17
백준 2225  (0) 2021.02.17
반응형

www.acmicpc.net/problem/2133

 

2133번: 타일 채우기

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

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// https://kosaf04pyh.tistory.com/236
#include <iostream>
using namespace std;
int n, dp[31];
int main() {
    cin >> n;
    if (n % 2 == 1) {
        cout << 0;
        exit(0);
    }
    dp[0] = 1;
    dp[2] = 3;
 
    for (int i = 4; i <= n; i++) {
        // 1. 오른쪽 2개 고정
        dp[i] = dp[i - 2] * 3;
        // 2. 오른쪽에 4개, 6개, ..., n개 고정    
        for (int j = 4; i >= j; j = j + 2) 
            dp[i] += dp[i - j] * 2;
    }
    cout << dp[n];
}
 cs
반응형

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

백준 11054  (0) 2021.02.19
백준 13398 [복습 필수]  (0) 2021.02.18
백준 11055  (0) 2021.02.17
백준 2225  (0) 2021.02.17
백준 1699  (0) 2021.02.17
반응형

www.acmicpc.net/problem/11055

 

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수

www.acmicpc.net

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
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001], dp[1001], ans;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)    {
        cin >> arr[i];
        dp[i] = arr[i];
    }
    
    ans = dp[0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + arr[i]);
                ans = max(ans, dp[i]);
            }
        }
    }
    cout << ans;
}
cs
반응형

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

백준 13398 [복습 필수]  (0) 2021.02.18
백준 2133 [복습 필수] (점화식)  (0) 2021.02.17
백준 2225  (0) 2021.02.17
백준 1699  (0) 2021.02.17
백준 1309  (0) 2021.02.17
반응형

www.acmicpc.net/problem/2225

 

2225번: 합분해

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

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int n, k, arr[201][201];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
        arr[i][1] = i;
    for (int i = 1; i <= n; i++)
        arr[1][i] = 1;
 
    for (int i = 2; i <= k; i++) {
        for (int j = 2; j <= n; j++)
            arr[i][j] = (arr[i - 1][j] + arr[i][j - 1]) % 1000000000;
    }
    cout << arr[k][n];
}
 cs
반응형

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

백준 2133 [복습 필수] (점화식)  (0) 2021.02.17
백준 11055  (0) 2021.02.17
백준 1699  (0) 2021.02.17
백준 1309  (0) 2021.02.17
백준 1932  (0) 2021.02.17
반응형

www.acmicpc.net/problem/1699

 

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll n, dp[100001];
 
int main() {
    cin >> n;
    fill(dp, dp + n + 1, 987654321);
    for (int i = 1; i * i <= n; i++)
        dp[i * i] = 1;
 
    // 1부터 n까지 채우기
    for (int i = 1; i <= n; i++) {
        // i 만들 수 있는 모든 경우의 수 다 해보기
        for (int j = 1; j * j <= i; j++)
            dp[i] = min(dp[i], 1 + dp[i - j * j]);
    }
    cout << dp[n];
}
cs
반응형

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

백준 11055  (0) 2021.02.17
백준 2225  (0) 2021.02.17
백준 1309  (0) 2021.02.17
백준 1932  (0) 2021.02.17
백준 1912  (0) 2021.02.17
반응형

www.acmicpc.net/problem/1309

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#define DIV 9901
using namespace std;
int n, dp[3][100001];
int main() {
    cin >> n;
    dp[0][1] = 1;    // 배치 안함
    dp[1][1] = 1;    // 1번 칸에 배치
    dp[2][1] = 1;    // 2번 칸에 배치
 
    for (int i = 2; i <= n; i++) {
        dp[0][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) % DIV;
        dp[1][i] = (dp[0][i - 1] + dp[2][i - 1]) % DIV;
        dp[2][i] = (dp[0][i - 1] + dp[1][i - 1]) % DIV;
    }
    cout << (dp[0][n] + dp[1][n] + dp[2][n]) % DIV;
    
}
cs
반응형

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

백준 2225  (0) 2021.02.17
백준 1699  (0) 2021.02.17
백준 1932  (0) 2021.02.17
백준 1912  (0) 2021.02.17
백준 2156  (0) 2021.02.17
반응형

www.acmicpc.net/problem/1932

 

1932번: 정수 삼각형

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
int n, dp[501][501], ans = -1;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            cin >> dp[i][j];
    }
 
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;
}
cs
반응형

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

백준 1699  (0) 2021.02.17
백준 1309  (0) 2021.02.17
백준 1912  (0) 2021.02.17
백준 2156  (0) 2021.02.17
백준14002  (0) 2021.02.15
반응형

www.acmicpc.net/problem/1912

 

1912번: 연속합

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

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, ans, arr[100001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n)
        cin >> arr[i];
    ans = arr[0];
    for (int i = 1; i < n;i++) {
        arr[i] = max(arr[i], arr[i - 1] + arr[i]);
        ans = max(ans, arr[i]);
    }
    cout << ans;
}
cs
반응형

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

백준 1309  (0) 2021.02.17
백준 1932  (0) 2021.02.17
백준 2156  (0) 2021.02.17
백준14002  (0) 2021.02.15
백준 15990  (0) 2021.02.15

+ Recent posts

티스토리툴바