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

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


n개의 종류 동전을 주고!

k원을 만들 수 있는 경우의 수를 구하는 문제입니다.

종류가 1, 2, 5이고..

10원을 만든다고 가정하면!


1원 = 1(1가지)

2원 = 1 + 1

        2

3원 = 1 + 1 + 1

   2 + 1

4원 = 1 + 1 + 1 + 1,

        1 + 1 + 2

        2 + 2

5원 = 1 + 1 + 1 + 1 + 1

        1 + 1 + 1 + 2

         2 + 2 + 1

         5

......

이렇게 갈 것입니다.

그렇다면 점화식을 어떻게 세워야할까요???



5원을 구한다고 생각하면

4원에서 + 1을 한 경우(1가지)

3원에서 + 2을 한 경우(2가지)

0원에서 + 5를 한 경우(1가지)

이렇게 총 4가지입니다.


해결 방법은..

1원에 대해서 먼저 dp를 채워줍니다.

그렇다면 k원까지 dp가 각각 1원으로 채워질 것입니다.


그리고 2원에 대해서 또 채워줍니다.

dp[2]의 값은 1에서 2가되겠지요(2가 추가되었으므로)

3원도 마찬가지로 1에서 2가되겠지요(1 + 2가 추가됨)

4원은 3이 될것입니다. 이유는(3 + 1과 2 + 2가 추가됨)


표로 그리면서 풀면 편할 것입니다..

이것을 점화식으로 세우면 아래의 코드와 같습니다.

coin[i]에 대해서 k원까지 돌고..

그 다음 코인에 대해서 k원까지 돌고...


1
2
3
4
5
6
7
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            if(j - coin[i] >= 0) dp[j] += dp[j - coin[i]];
        }
    }
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
#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);
 
    dp[0] = 1;
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            if(j - coin[i] >= 0) dp[j] += dp[j - coin[i]];
        }
    }
    printf("%d\n", dp[k]);
    
    return 0;
}
cs


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

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

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


이분 탐색할 것은.. 각 나무당 몇 미터를 자를 것이냐 ? 입니다.

이 문제는 꽤 쉬우므로..


해당 나무의 높이 보다 더 높이 자를 경우 -의 나무는 없으므로 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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define MAX_SIZE 1000000
 
int height[MAX_SIZE];
 
int main()
{
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    int max_height = 0;
 
    for(int i = 0; i < n; i++) scanf("%d", height + i);
    for(int i = 0; i < n; i++) max_height = height[i] > max_height ? height[i] : max_height;
 
    int left = 1, right = max_height;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        long long sum = 0;
 
        for(int i = 0; i < n; i++) sum += height[i] - mid > 0 ? height[i] - mid : 0;
 
        if(sum < m) right = mid - 1;
        else left = mid + 1;
    }
 
    printf("%d\n", right);
 
    return 0;
}
 
cs


'알고리즘 > 이분 탐색' 카테고리의 다른 글

[2585] 경비행기  (0) 2017.08.30
[12842] 튀김 소보루  (0) 2017.08.23
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19

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


이 문제는 각 나라에 배정할 예산을 탐색하면 됩니다.

조심할 점은 내가 탐색할 예산액보다 요구하는 양이 적은 지방은 다 주지말고 그냥 전체 예산액에서 빼줘야한다는 점과

더 많은 지방에는 예산액만큼만 줘야한다는 점입니다. 이 두개만 조심하면 쉬운 문제인 것 같습니다.


아 추가로.. 만약 각 지방이 요구하는 금액이 국가 에산보다 적을 시에는 그냥 요구하는 금액만큼 주면되므로 그 중 최대값을 출력하면됩니다.

아래의 코드입니다.

1
2
3
4
5
6
7
    for(int i = 0; i < n; i++)
    {
        tmp -= money[i];
        max_money = money[i] > max_money ? money[i] : max_money;
    }
 
    if(tmp >= 0) return printf("%d\n", max_money), 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
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <algorithm>
#include <iostream>
 
#define MAX_SIZE 10000
#define INF 1e9
 
using namespace std;
 
int money[MAX_SIZE];
 
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &money[i]);
 
    int total;
    scanf("%d", &total);
 
    int tmp = total;
    int max_money = 0;
 
    for(int i = 0; i < n; i++)
    {
        tmp -= money[i];
        max_money = money[i] > max_money ? money[i] : max_money;
    }
 
    if(tmp >= 0) return printf("%d\n", max_money), 0;
 
    int left = total / n, right = max_money;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        tmp = total;
 
        for(int i = 0; i < n; i++)
        {
            if(mid >= money[i]) tmp -= money[i];
            else tmp -= mid;
        }
 
        if(tmp >= 0) left = mid + 1;
        else right = mid - 1;
    }
 
    printf("%d\n", right);
 
    return 0;
}
 
cs


'알고리즘 > 이분 탐색' 카테고리의 다른 글

[12842] 튀김 소보루  (0) 2017.08.23
[2805] 나무 자르기  (3) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19

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

이분탐색 문제의 해결방법은 계속 강조하지만 무엇을 탐색할 것인가?를 고민하면됩니다.
(물론 이 문제가 이분탐색인가?? 라는 것을 알기가 힘들긴 합니다..)


이 문제는 블루레이의 크기를 최소로 만들면 됩니다..


굳이 조심해야할 점은 마지막에 레쓴이 남았을 때 CD를 한장 더만들어줘야한다는 점..??


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
#include <cstdio>
#include <algorithm>
#include <iostream>
 
#define MAX_SIZE 100000
#define INF 1e9
 
using namespace std;
 
int lesson[MAX_SIZE];
 
int main()
{
    int n, c;
    scanf("%d %d", &n, &c);
 
    int max_lesson = 0;
 
    for(int i = 0; i < n; i++)
    {
        scanf("%d", lesson + i);
        max_lesson = lesson[i] > max_lesson ? lesson[i] : max_lesson;
    }
 
    int left = max_lesson, right = INF / c;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int sum = 0;
        int bluelay = 0;
 
        for(int i = 0; i < n; i++)
        {
            if(sum + lesson[i] > mid)
            {
                sum = 0;
                bluelay++;
            }
            sum += lesson[i];
        }
 
        if(sum != 0) bluelay++;
 
        if(bluelay <= c) right = mid - 1;
        else left = mid + 1;
    }
 
    printf("%d\n", left);
 
    return 0;
}
 
cs


'알고리즘 > 이분 탐색' 카테고리의 다른 글

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

+ Recent posts

티스토리툴바