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


이 문제는 어렵지 않았습니다.

dp라고 알 수 있는 부분은 이 문제가 경우의 수이고, 정답이 2^63이라면 DP를 제외하고는 시간안에 풀 수 없습니다.


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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
 
using namespace std;
 
typedef long long ll;
 
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
 
int map[100][100];
ll dp[100][100];
 
int n;
 
ll f(int x, int y) {
    if (x == n - 1 && y == n - 1) {
        return 1;
    }
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i] * map[x][y];
        int ny = y + dy[i] * map[x][y];
        if (nx >= n || ny >= n) continue;
 
        ret += f(nx, ny);
    }
 
    return ret;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
 
    cout << f(0, 0);
 
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1365] 꼬인 전깃줄  (0) 2017.09.16
[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24

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


2차원 DP로 정의하시면 쉽게 해결할 수 있습니다.


dp[자리수][현재 수]라고 정의하면 되겠습니당.


그리고 dfs안에서 포문은 자기 자신과 같거나 큰수로 이동하면 되겠습니다!!!!!!!!!!!!


코드입니당!~_~

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
ll dp[65][10];
int n;
 
ll f(int d, int now) {
    if (d == n) return 1;
 
    ll &ret = dp[d][now];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = now; i < 10; i++) {
        ret += f(d + 1, i);
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(dp, -1, sizeof(dp));
 
        cin >> n;
 
        ll ret = 0;
        for (int i = 0; i < 10; i++) ret += f(1, i);
 
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1890] 점프  (0) 2017.09.15
[2565] 전깃줄  (0) 2017.09.07
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24

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


전형적인 DP문제네요.

1차원 DP이구요

정의는 n까지가는데 최소 비용이라고 정의하면 되겠습니다.


메모이제이션을 하면서 재귀를 돌렸습니다.


문제 풀 떄 꿀팁은 인풋을 받을 때가 중요합니다.

B = 0

O = 1

J = 2

로 배열에 저장했습니다.


그래서 B다음에 O로 갈 땐 (arr[현재 위치] + 1) % 3 == arr[다음 위치] 이 조건이 성립하는 곳으로 이동하시면 됩니다.


코드입니다.

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
#include <iostream>
#include <vector>
 
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int street[1000];
 
int dp[1000];
int n;
 
int min(int a, int b) {
    return a < b ? a : b;
}
 
int dfs(int pos) {
    if (pos == n - 1) return 0;
 
    int &ret = dp[pos];
    if (ret != -1) return ret;
    ret = INF;
    
    for (int i = pos + 1; i < n; i++) if(street[i] == (street[pos] + 1) % 3) ret = min(ret, dfs(i) + (i - pos) * (i - pos));
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'B') street[i] = 0;
        else if (c == 'O') street[i] = 1;
        else street[i] = 2;
    }
 
    memset(dp, -1, sizeof(dp));
 
    int ret = dfs(0);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09

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



이 문제는


두가지로 dp를 정의해보았습니다.


첫번째로 풀 때는

dp[날짜][지각 수][현재 날짜의 전 전에 결석했는지][현재 날짜의 전 날에 결석했는지]

라고 처음에 정의했습니다.


근데 이 방법보다 간단하게 정의할 수 있습니다.

3차원 dp인데요


dp[날짜][지각 수][연속으로 결석한 수] 라고 정의할 수 있습니다.

연속으로 결석한 수 라고 정의한 이유는


결석한 수가 연속이지 않으면 0으로 초기화하면 되기 때문입니다.


아래는 두번째 방법 풀 코드입니다.

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
#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e6
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[1001][2][3];
int n;
 
int f(int date, int late, int absence) {
    if (late == 2) return 0;
    else if (absence == 3) return 0;
    
    if (date == n) return 1;
        
    int &ret = dp[date][late][absence];
    if (ret != -1) return ret;
    ret = 0;
 
    ret += f(date + 1, late + 1, 0) + f(date + 1, late, absence + 1) + f(date + 1, late, 0);
 
    return ret % MOD;
}
 
 
int main() {
    cin >> n;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0, 0);
    return 0;
}
 
cs

이 아래는 첫번째 방법입니다.

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>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e6
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[1001][3][2][2];//date/late/1 2 3 
int n;
 
int f(int date, int late, int pprev, int prev) {
    if (date == n) return 1;
    int &ret = dp[date][late][pprev][prev];
    if (ret != -1) return ret;
    ret = 0;
 
    if (pprev && prev) {
        if (late < 1) ret += f(date + 1, late + 1, prev, 0) % MOD;
        ret += f(date + 1, late, prev, 0) % MOD;
    }
    else {
        if (late < 1) ret += f(date + 1, late + 1, prev, 0) % MOD;
        ret += f(date + 1, late, prev, 1) % MOD;
        ret += f(date + 1, late, prev, 0) % MOD;
    }
 
    return ret % MOD;
}
 
 
int main() {
    cin >> n;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0, 0, 0);
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2688] 줄어들지 않아  (0) 2017.07.27
[12026] BOJ 거리  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[1102] 발전소  (0) 2017.07.08

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


이 문제는 2차원 dp로 간단하게 해결할 수 있습니다.

dp[sum][수를 쓴 수]라고 정의를 했습니다.


저는 dfs를 이용해서 메모이제이션했는데요

만약 sum이 N을 초과하면 0을 리턴합니다 더 들어갈 필요도 없기 때문입니다.

만약 해당 깊이(수를 쓴 수와 같음)가 되었는데 내가 원하는 N이 아니라면 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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (int)1e9
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int dp[201][201];
int n, k;
 
int f(int sum, int d) {
    if (sum > n) return 0;
    if (d == k) {
        if (sum == n) return 1;
        else return 0;
    }
 
    int &ret = dp[sum][d];
    if (ret != -1) return ret;
 
    ret = 0;
 
    for (int i = 0; i <= n; i++) {
        ret += f(sum + i, d + 1);
        ret %= MOD;
    }
 
    return ret;
}
 
int main() {
    cin >> n >> k;
 
    memset(dp, -1, sizeof(dp));
 
    cout << f(0, 0);
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04

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


처음에 그리디로 접근했는데.. 생각해보니 잘못된 접근이었습니다.

1, 10, 25, 100, 1000, 2500, ... 이렇게 코인이 진행되는데

이 수들이 서로 배수라면 그리디로 해결해도 괜찮지만

10에서 25, 1000에서 2500 ...... 이런식으로 배수가 아닌 경우가 존재합니다.


그렇기 떄문에 그리디는 잘못된 방법입니다.


다음에 생각한 방법이 재귀를 이용하여 완전탐색으로 해봤습니다.

결과는 잘나오나 어떤 부분이 틀린지 잘모르겠습니다.


그래서 블로그를 찾다 보니 푸는 방법이 굉장히 신기했습니다.


1, 10, 25

100, 1000, 2500

10000, 100000, 250000

.

.

.

한단계 단계가 100으로 나눌 떄 같아지는 것을 이용한 풀이입니다.


dp를 이용해서

0~99까지 최소 코인 수를 구합니다.


그 후에 입력 받은 n을 100씩 나누면서 더해주면 답이 되는 문제입니다..

어떻게 생각하지 ..ㅡ.ㅡ..... 천재들...


아래는 풀 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 1000000
#define MAX_SIZE 101
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int main() {
    int coin[] = { 1, 10, 25 };
    int dp[100] = { 0, };
 
    for (int i = 1; i < 100; i++) {
        dp[i] = INF;
        for (int j = 0; j < 3; j++) {
            if (i - coin[j] >= 0) {
                dp[i] = min(dp[i], dp[i - coin[j]] + 1);
            }
        }
    }
 
    int t;
    cin >> t;
 
    while (t--) {
        ll n;
        cin >> n;
 
        ll ret = 0;
 
        while (n) {
            int nMod100 = n % 100;
 
            ret += dp[nMod100];
            n /= 100;
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
 
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27

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


처음엔 on과 off인 부분을 나눠서

그리디로 접근을 하려고 했었는데

1-2로 가는데 5, 2-3으로 가는데 20

1-4로 가는데 10, 4-5로 가는데 5이고, YNNNN, p = 3이라면

1-4-5 루트가 나와야하는데 1-2-3 루트가 나옵니다.


짱돌을 엄청나게 굴렸지만.... 생각이 잘안났습니다.

그래서 분류를 봤는데

dp와 비트마스크로 해결하는 문제였습니다.


저는 2차원 dp로 해결했습니다.

dp[on 발전소 갯수][발전소의 상태]라고 정의했습니다.

사실 발전소의 상태로 발전소의 개수를 알 수 있지만 편의를 위해 이렇게 해결했습니다.


문제에서 적어도 p개라고 했는데 p개 초과일 경우가 p개인 경우보다 코스트가 작아지는 경우는 없으므로

탈출조건은 발전소 갯수가 p이상일 때 탈출시켰습니다.


아래는 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 16
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][1 << 16];
int n, p;
int on;
int onCnt;
 
int f(int cnt, int on) {
    if (cnt >= p) return 0;
 
    int &ret = dp[cnt][on];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < n; i++) {
        if(on & 1 << i){
            for (int j = 0; j < n; j++) {
                if (i == j || on & (1 << j)) continue;
                ret = min(ret, f(cnt + 1, on | 1 << j) + spend[i][j]);
            }
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'Y') on |= 1 << i, onCnt++;
    }
 
    cin >> p;
 
    memset(dp, -1, sizeof(dp));
 
    int ret = f(onCnt, on);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27
[1915] 가장 큰 정사각형  (0) 2017.06.07

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


3차원 dp문제입니다.


dp정의는

dp[인덱스][인접한 비트 수][현재 비트]라고 정의할 수 있습니다.


ex)

예제로 

n = 6이고 k=2일 때를 들어보겠습니다.

만약에 

dfs를 이용하여 0,1,1,1까지 들어와서 그다음에 깊이 6까지 들어갔다왔다고 생각해보면.


1. 00111-0

2. 00111-1


이렇게 2가지의 경우가 있겠죠

인접한 비트 수가 2인 경우는 1번하나겠죠!


근데 11011라는 수로 들어왔다고 칩시다!

그 다음으로 들어갈 필요가 있을까요??

아니요 없습니다!!


이유는 위의 00111경우에서


현재 인덱스가 5이고 인접한 비트 수가 2이고 현재 비트가 1인 경우에 1가지 밖에 없다는 것을 알았기 떄문에

굳이 다시 들어갈 필요가 없는 것입니다.

00111의 경우도

마찬가지로

11011-0과

11011-1

두가지 중 1번만 가능한 경우이기 때문입니다.


ret += f(d + 1, adj, 0);

ret += f(d + 1, adj + bit * 1, 1);


이 코드에서 윗 줄은 다음 비트가 0이기 때문에 다음으로 넘어갈때 인접한 비트 수가 증가할 수 없어서 특별한 연산 없이 adj를 삽입합니다.

두번째 줄은 내 비트가 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
49
50
51
52
53
54
55
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 101
 
using namespace std;
int n, k;
int dp[MAX_SIZE][MAX_SIZE][2];
 
int f(int d, int adj, int bit) {
    if (d == n - 1) {
        if (adj == k) return 1;
        else return 0;
    }
 
    int &ret = dp[d][adj][bit];
    if (ret != -1) return ret;
    ret = 0;
 
    ret += f(d + 1, adj, 0);
    ret += f(d + 1, adj + bit * 1, 1);
 
    return ret;
}
 
int main() {
 
    int t;
    scanf("%d", &t);
 
    while (t--) {
        scanf("%d %d", &n, &k);
        memset(dp, -1, sizeof(dp));
 
        int ret = 0;
        for (int i = 0; i < 2; i++) {
            ret += f(0, 0, i);
        }
 
        printf("%d\n", ret);
    }
    return 0;
 
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2158] 동전 교환  (0) 2017.07.09
[1102] 발전소  (0) 2017.07.08
[1029] 그림 교환  (0) 2017.06.27
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25

+ Recent posts

티스토리툴바