반응형

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

www.acmicpc.net/problem/2156

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

비슷한 문제: www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

방법 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
#include <iostream>
#include <algorithm>
using namespace std;
long long n, ans = -1, arr[10001], dp[10001];
int main() {
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    dp[1] = arr[1];
    dp[2] = arr[2] + arr[1];
    ans = max(dp[1], dp[2]);
 
    /*
        반례
        6
        1000 1000 1 1 1000 1000
    */
    for (int i = 3; i <= n; i++) {
        // 1. i번째 잔 마심
        dp[i] = arr[i] + max(arr[i - 1] + dp[i - 3], dp[i - 2]);
        // 2. i번쨰 잔 안 마심
        dp[i] = max(dp[i - 1], dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;
}
 cs

방법 2. 이차원 배열로 풀기

 

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 n, arr[10001], dp[3][10001];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    dp[0][1] = 0;        // 0번 연속 마심 (i번째 X)
    dp[1][1] = arr[1];    // 1번 연속 마심 (i번째 O, i-1번째 X)
    dp[2][1] = arr[1];    // 2번 연속 마심 (i번째 O, i-1번째 O)
    
    dp[0][2] = arr[1];
    dp[1][2] = arr[2];
    dp[2][2] = arr[1] + arr[2];
 
 
    for (int i = 3; i <= n; i++) {
        dp[0][i] = max(dp[0][i - 1], max(dp[1][i - 1], dp[2][i - 1]));
        dp[1][i] = arr[i] + dp[0][i - 1];
        dp[2][i] = arr[i] + dp[1][i - 1];
    }
 
    cout << max(dp[0][n], max(dp[1][n], dp[2][n])) << endl;
}
 cs

 

 

반응형

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

백준 1932  (0) 2021.02.17
백준 1912  (0) 2021.02.17
백준14002  (0) 2021.02.15
백준 15990  (0) 2021.02.15
백준 11052  (0) 2021.02.15
반응형

www.acmicpc.net/problem/14002

 

14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

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
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 <stack>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
stack<int> s;
int n, ans, idx, arr[1001], dp[1001], index[1001];
void func(int idx) {
    if (idx == -1) return;
    s.push(arr[idx]);
    func(index[idx]);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n) {
        cin >> arr[i];
        dp[i] = 1;
        index[i] = -1;
    }
 
    rep(i, n) {
        rep(j,i){
            if (arr[i] > arr[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    index[i] = j;
                }
            }
        }
    }
 
    // dp 최댓값, 인덱스 찾기
    rep(i, n) {
        if (dp[i] > ans) {
            ans = dp[i];
            idx = i;
        }
    }
    cout << ans << '\n';
    // index 배열 탐색
    func(idx);
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
}
cs
반응형

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

백준 1912  (0) 2021.02.17
백준 2156  (0) 2021.02.17
백준 15990  (0) 2021.02.15
백준 11052  (0) 2021.02.15
백준 9095  (0) 2021.02.15
반응형

www.acmicpc.net/problem/15990

 

15990번: 1, 2, 3 더하기 5

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

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
#include <iostream>
using namespace std;
#define DIV 1000000009
long long t, n, dp[4][100001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    dp[1][1] = 1;
    dp[2][2] = 1;
    dp[1][3] = 1;
    dp[2][3] = 1;
    dp[3][3] = 1;
    for (long long i = 4; i <= 100000; i++) {
        dp[1][i] = (dp[2][i - 1] + dp[3][i - 1]) % DIV;
        dp[2][i] = (dp[1][i - 2] + dp[3][i - 2]) % DIV;
        dp[3][i] = (dp[1][i - 3] + dp[2][i - 3]) % DIV;
    }
    cin >> t;
    while (t--) {
        cin >> n;
        cout << (dp[1][n] + dp[2][n] + dp[3][n]) % DIV << '\n';
    }
}
cs
반응형

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

백준 2156  (0) 2021.02.17
백준14002  (0) 2021.02.15
백준 11052  (0) 2021.02.15
백준 9095  (0) 2021.02.15
백준 1520 [복습 필수]  (0) 2021.01.30
반응형

www.acmicpc.net/problem/11052

 

11052번: 카드 구매하기

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,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=1;i<=n;i++)
using namespace std;
int n, arr[1001], dp[1001];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> arr[i];
        dp[i] = arr[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i / 2; j++) {
            dp[i] = max(dp[i], arr[j] + dp[i - j]);
        }
    }
    cout << dp[n];
}
cs
반응형

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

백준14002  (0) 2021.02.15
백준 15990  (0) 2021.02.15
백준 9095  (0) 2021.02.15
백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
반응형

www.acmicpc.net/problem/14391

 

14391번: 종이 조각

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×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
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
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int arr[5][5], direction[5][5], visited[5][5];
int n, m;
int val = 0;
int total = 0;
int ans = -1;
int cur;
int temp = 0;
void func(int x, int y) {
    while(1){
        if (x >= n || y >= m || cur != direction[x][y]) {
            total += temp;
            temp = 0;
            return;
        }
        if (visited[x][y])
            return;
        visited[x][y] = 1;
        temp = temp * 10 + arr[x][y];
        if (direction[x][y] == 0)
            y++;
        else
            x++;
    }
}
int main() {
    cin >> n >> m;
    rep(i, n) {
        rep(j, m) {
            char c;
            cin >> c;
            arr[i][j] = c - '0';
        }
    }
 
    while (val < (1 << (n * m))) {
        // 1. val -> direction[][]
        int idx = 0;
        while (idx < n*m) {
            int nx = idx / m;
            int ny = idx % m;
            direction[nx][ny] = (val >> idx) & 1;
            idx++;
        }
        // 2. arr, direction, visited
        memset(visited, 0, sizeof(visited));
        total = 0;
        rep(i, n) {
            rep(j, m) {
                if (!visited[i][j]) {
                    cur = direction[i][j];
                    func(i,j);
                }
            }
 
        }
        ans = max(ans, total);
        val++;
    }
    cout << ans;
}
cs
반응형

'백준 > 브루트포스' 카테고리의 다른 글

백준 1208 [복습 필수]  (0) 2021.03.06
백준 14225  (0) 2021.02.23
백준 1182  (0) 2021.02.15
백준 6064  (0) 2021.02.13
백준 1107 [복습 필수]  (0) 2021.02.13

+ Recent posts

티스토리툴바