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

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



처음에 dfs로 방문체크를 하면서 cost가 크거나 같으면 이동하는 식으로 해서 해결해보려고 했으나

65프로에서 시간초과가 뜨더군요.

제한시간이 2초인데

dfs로 하면 최악의 경우 15!의 시간이 걸리기 때문에 해결할 수 없었습니다.


그래서 dp를 이용해야 했는데..

방문한 곳의 상태가 필요했기 때문에 비트마스크를 사용했습니다.


제 dp의 정의는


dp[1 << 15][15][10] : 방문상태, 아티스트 번호, 비용으로 정의했습니다.


아래는 코드입니다.


f함수의 매개변수는 방문상태, 아티스트 번호, 코스트, 깊이 입니다.



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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 15
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int dp[1 << MAX_SIZE][MAX_SIZE][10]; //state, artistNumber, cost
int cost[MAX_SIZE][MAX_SIZE];
int n;
 
int f(int state, int artist, int c, int d) {
    int &ret = dp[state][artist][c];
    if (ret != 0) return ret;
    ret = d;
 
    for (int i = 0; i < n; i++) {
        if (state & (1 << i) || cost[artist][i] < c) continue;
        ret = max(ret, f(state | (1 << i), i, cost[artist][i], d + 1));
    }
    return ret;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &cost[i][j]);
        }
    }
 
    printf("%d", f(1, 0, 0, 1));
    
    return 0;
}
cs


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

[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20

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


요즘 나태해져서.. 다시 열심히 해야겠습니다 ㅎㅎ!!

DP문제입니다!


간단하게 생각하면 별로 안어려운 문제인 것 같습니다!


딱봐도..4인데... 어떻게 dp로 접근했냐하면


for문은 행우선으로 진행하면 됩니다. 행의 모든 열을 다 돌면 다음행!


그리고 중요한 것은 해당 배열의 위, 왼쪽, 그리고 왼쪽위 대각선 이 세방향을 검사했습니다.


내가 1이고 그 세 개중에 가장 작은 값(0은 제외) + 1이 결국 정사각형의 변의 길이입니다.


예제를 보면서 해결해보도록하죠!


4 4

0100

0111

1110

0010


dp테이블을 써보도록하겠습니다.

0100
0111
1120
0010

최대 변의 길이는 2겠지요!?!
그래서 정답은 2 * 2 = 4입니다!!!!!!!!!!!!!!

아래는 코드입니다.
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
#include <cstdio>
#define MAX_SIZE 1000
#define INF 0x7fffffff
 
bool arr[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
 
    int m, n;
    scanf("%d %d", &m, &n);
 
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }
 
    int ret = 0;
    int dx[3] = { 0, -1, -1 };
    int dy[3] = { -1, 0, -1 };
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!arr[i][j]) continue;
 
            int min_value = INF;
            for (int k = 0; k < 3; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (nx < 0 || ny < 0) {
                    min_value = 0;
                    break;
                }
                min_value = min(min_value, dp[nx][ny]);
            }
            if (!min_value) dp[i][j] = 1;
            else if (min_value != INF) dp[i][j] = min_value + 1;
 
            ret = max(dp[i][j], ret);
        }
    }
 
    printf("%d\n", ret * ret);
 
    return 0;
}
cs


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

[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27
[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20

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


이 문제가 어려운 이유는 반대쪽 저울에 추를 올릴 수 있다는 점입니다.

문제의 예제처럼 1과 4의 추가 있을 때 검사할 수 있는 무게는


0, 1, 4

그리고

(1 + 4), (4 - 1)


이렇게 다섯가지 입니다. 어려운 부분은 (4 - 1)이겠죠.


문제의 조건을 보면 추의 최대 개수 30개, 추의 최대 무게 500g, 확인할 무게 최대 7개입니다.


dp정의는 dp[n][k] = n번 추까지 사용했을 때 k라는 무게를 만들 수 있는지 (bool) 입니다.


n번째 추에서 나눠지는 경우는 세가지가 있습니다. 추를 왼쪽 저울에 올릴지, 안올릴지, 아니면 오른쪽 저울(편의상 검사할 무게를 오른쪽)에 올릴지 입니다.


이렇게 한다면 시간복잡도는 30개 * 3가지 경우 * 15000(500g * 30)입니다만... 저는 dp배열을 30001로 잡았습니다.

이유는 -값도 저장하기 위해서입니다. dp[][15000]이 0의 무게를 나타내며 14999는 -1, 15001은 1입니다. 30000이면 15000이겠죠??


아래는 풀코드입니다.

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
bool dp[31][30001];
int weight[31];
int m[3] = {-1, 0, 1};
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i = 1; i <= n; i++) scanf("%d", &weight[i]);
 
    dp[0][15000] = 1; // 0은 추가 없어도 만들 수 있음.
    for(int i = 1; i <= n; i++) // i번째 추
    {
        for(int j = 0; j < 3; j++)//-1, 0, 1
        {
            for(int k = 0; k <= 30000; k++) // -15000 ~ 15000
            {
                int tt = weight[i] * m[j] + k; // k무게에다가 해당 추를 왼쪽 혹은 오른쪽저울에 올리던지 아니면 안올리던지
                dp[i][tt] += dp[i - 1][k]; // i - 1번째 인덱스까지 k무게가 존재한다면 dp[i][tt]도 존재하게 됨.
            }
        }
    }
 
 
    int nn;
    scanf("%d", &nn);
 
    for(int i = 0; i < nn; i++)
    {
        int ret;
        scanf("%d", &ret);
        printf("%c ", dp[n][ret + 15000] ? 'Y' : 'N');
    }
 
    puts("");
    return 0;
}
 
cs


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

[1029] 그림 교환  (0) 2017.06.27
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19

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



이 문제의 핵심은 맨 위칸 혹은 맨 아래칸이 전부 2 * 1의 타일로 채워졌을 때 입니다. 물론 2 * 1 타일 개수는 2개 이상일 때!

2개 일 때 2개! 3개일 때도 2개, 4개일 때도 2개 !!


그러므로 점화식은 아래와 같습니다!


1
2
3
4
5
    for(int i = 3; i <= n; i++){
        dp[i] += dp[i - 2] * 3;
        
        for(int j = 4; j <= i; j += 2) dp[i] += dp[i - j] * 2;
    }
cs


위의 점화식은 2칸일 때 3가지의 경우가 존재하므로 !


아래 점화식은 위에서 설명한 경우 입니다.!


풀코드입니다.


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 <cstdio>
#define MAX_SIZE 31
 
int dp[MAX_SIZE];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    dp[0] = 1;
    dp[1] = 0;
    dp[2] = 3;
    for(int i = 3; i <= n; i++){
        dp[i] += dp[i - 2] * 3;
        
        for(int j = 4; j <= i; j += 2) dp[i] += dp[i - j] * 2;
    }
 
    printf("%d\n", dp[n]);
 
    return 0;
}
 
cs


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

[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25
[1309] 동물원  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19
[2293] 동전 1  (4) 2017.04.19

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


다른 분들은.. 도대체 어떻게 푸신건지.. 잘 이해가 안가더라구요...ㅎㅎ...

저는.. 좀 어렵게 푼듯 하네요... 다른분들은 1차원 dp인데 저는 2차원 dp라고 생각했습니다.


dp[N][3]으로 2차원 dp를 정의했고

N은 칸 수 뒤의 3은


0 = N번째 칸에 사자를 안넣는 경우

1 = 1번째 칸에 사자를 넣는 경우

2 = 2번쨰 칸에 사자를 넣는 경우


라고 생각하고 풀었습니다.


n칸에다가 사자를 안넣는다면

dp[n][0]은 dp[n - 1][0] + dp[n - 1][1] + dp[n - 2][2]입니다.

n칸에다가 사자를 안넣는 경우는 n - 1 칸에서 사자를 안넣는경우, 사자를 1칸에 넣는 경우, 2칸에 넣는경우 셋 다 가능하기 때문입니다.


n의 1칸에 사자를 넣는다면 n-1칸에서는 사자를 안넣거나 2칸에 넣는다면 n의 1칸에 사자를 넣을 수 있으므로 그 두개를 더합니다.


n의 2칸에서는 1칸과 동일하게 n - 1칸에 사자를 안넣는 경우, 1칸에 넣는 경우 두가지를 더합니다.


점화식은..

1
2
3
4
5
6
for(int i = 2; i <= n; i++)
{
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
    dp[i][1] = dp[i - 1][0] + dp[i - 1][2];
    dp[i][2] = dp[i - 1][0] + dp[i - 1][1];
}
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
#include <cstdio>
#define MAX_SIZE 100001
 
int dp[MAX_SIZE][3];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i = 0; i < 3; i++) dp[1][i] = 1;
 
    for(int i = 2; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
        dp[i][1] = dp[i - 1][0] + dp[i - 1][2];
        dp[i][2] = dp[i - 1][0] + dp[i - 1][1];
 
        for(int j = 0; j < 3; j++) dp[i][j] %= 9901;
    }
    printf("%d\n", (dp[n][0] + dp[n][1] + dp[n][2])%9901);
 
    return 0;
}
 
cs


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

[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19
[2293] 동전 1  (4) 2017.04.19
[1727] 커플 만들기  (0) 2017.04.05

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



동전2 문제는 최소의 동전을 써서 k원을 만드는 문제입니다.


dp[n] = n원을 만드는데 드는 최소의 동전 수

라고 정의를 하면 쉽습니다.

그렇다면 점화식은

dp[n] = dp[n - coin[i]] + 1

이 되겠지요???


근데 여기서 조심해야할 것은 두가지가 있습니다!


1. n에서 코인을 뺏을 떄 -가 될 수 있다.

2. n - coin[i]가 만들 수 없는 경우일 때 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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
int coin[MAX_SIZE];
int dp[10001];
 
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
 
    for(int i = 0; i < n; i++) scanf("%d", coin + i);
 
    for(int i = 1; i <= k; i++)
    {
        dp[i] = INF;
 
        for(int j = 0; j < n; j++)
        {
            int before = i - coin[j];
            if(before >= 0 && dp[before] != INF) dp[i] = min(dp[i], dp[before] + 1);
        }
    }
 
    printf("%d\n", dp[k] == INF ? -1 : dp[k]);
 
    return 0;
}
cs


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

[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20
[2293] 동전 1  (4) 2017.04.19
[1727] 커플 만들기  (0) 2017.04.05
[2240] 자두나무  (0) 2017.04.05

+ Recent posts

티스토리툴바