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

커플 만들기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB129934023227.008%

문제

여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.

당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.

입력

첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.

출력

첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.

예제 입력 

2 1
10 20
15

예제 출력 

5

힌트



















풀다가 머리에 쥐나서.. 섬광탄 맞은 것처럼 띵~~~하게 하는 난이도네요..(라헬이..생각나고..)

처음에 dp인줄도 모르고 그리디로 풀어서 엄청 틀렸네요..



이 문제를 풀 때 꿀팁은 항상 여자 혹은 남자의 데이터 수가 많다고 생각하고 푸는 것입니다.

저는 무조건 여자가 많게 만들어서 풀었습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
    scanf("%d %d", &m, &g);
 
    for(int i = 0; i < m; i++) scanf("%d", data1 + i);
    for(int j = 0; j < g; j++) scanf("%d", data2 + j);
 
    if(m > g)
    {
        swap(data1, data2);
        swap(m, g);
    }
 
    sort(data1, data1 + m);
    sort(data2, data2 + g);
cs


인풋과 정렬까지 하는 부분입니다.

만약 m(남자)가 크면 g(여자)와 swap을 해서 데이터를 바꿔줍니다.


남자의 데이터(1, 2, 3, 4), 여자의 데이터(a,b,c,d,e,f,g)라고 가정하겠습니다.


1

2

3

4


1가 선택할 수 있는 여자는 a,b,c,d입니다.


a

b

c

d

e

f

g


2가 선택할 수 있는 여자는 b,c,d,e입니다.

a

b

c

d

e

f

g


3이 선택할 수 있는 여자는 c,d,e,f입니다.


a

b

c

d

e

f

g


4가 선택할 수 있는 여자는 d,e,f,g입니다.


a

b

c

d

e

f

g



dp는 2차원으로 정의합니다.


dp[남자][여자] = 남자가 여자를 선택했을 때 까지 궁합의 합의 최솟값입니다.


예를 들어 1번 남자가 b번 여자를 선택한다면 2번 남자는 c,d,e만 선택할 수 있습니다.


dp[1][a]는 (1번 남자 성격) - (a번 여자 성격)의 절대값입니다.


그리고 dp[1][b]는 (1번 남자 성격) - (b번 여자 성격)의 절대값과 dp[1][a] 둘 중에 작은 값을 선택해서 저장합니다.

이 작업을 dp[1][d]까지 반복합니다.


점화식으로 표현하면 이 부분은 i == 0일 때 입니다.

1
2
3
4
5
6
7
8
    for(int i = 0; i < m; i++)
    {
        if(i == 0)
        {
            dp[0][0] = abs(data1[0] - data2[0]);
 
            for(int j = 1; j < g - (m - i - 1); j++) dp[i][j] = min(dp[i][j - 1], abs(data1[0] - data2[j]));
        }
cs


이후에 2-b를 연결한다고 생각하면 2-b의 절대값에 1-a를 더합니다. 그리고 dp[2][b]에 그 값을 저장합니다.


2-c를 연결한다고 생각하면 2-c의 절대값을 구하여서 dp[1][b]까지의 최솟값에 더하고 dp[2][b]값과 비교하여 작은 값을 저장합니다.

이 부분이 핵심이며.. 이 작업을 반복하면 정답을 구할 수 있습니다.


1
2
3
4
5
6
7
8
        else
        {
            for(int j = i; j < g - (m - i - 1); j++)
            {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + abs(data1[i] - data2[j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + abs(data1[i] - data2[j]), dp[i][j - 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
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
 
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define MAX_SIZE 1010
#define MAX_MOVE 31
 
using namespace std;
 
typedef pair<int, int> p;
 
int data1[MAX_SIZE];
int data2[MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
int m, g;
 
int abs(int a)
{
    if(a>=0) return a;
    else return -a;
}
 
int main()
{
    scanf("%d %d", &m, &g);
 
    for(int i = 0; i < m; i++) scanf("%d", data1 + i);
    for(int j = 0; j < g; j++) scanf("%d", data2 + j);
 
    if(m > g)
    {
        swap(data1, data2);
        swap(m, g);
    }
 
    sort(data1, data1 + m);
    sort(data2, data2 + g);
 
    for(int i = 0; i < m; i++)
    {
        if(i == 0)
        {
            dp[0][0] = abs(data1[0] - data2[0]);
 
            for(int j = 1; j < g - (m - i - 1); j++) dp[i][j] = min(dp[i][j - 1], abs(data1[0] - data2[j]));
        }
        else
        {
            for(int j = i; j < g - (m - i - 1); j++)
            {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + abs(data1[i] - data2[j]);
                else dp[i][j] = min(dp[i - 1][j - 1] + abs(data1[i] - data2[j]), dp[i][j - 1]);
            }
        }
    }
 
    printf("%d\n", dp[m - 1][g - 1]);
 
    return 0;
} 
 
cs


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

[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19
[2293] 동전 1  (4) 2017.04.19
[2240] 자두나무  (0) 2017.04.05

자두나무 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB230498566940.993%

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

예제 입력 

7 2
2
1
1
2
2
1
1

예제 출력 

6

힌트















DP는 식을 정의를 하는 것이 가장 중요하다고 생각합니다.

문제가 '매 초마다 두 개의 나무에서 떨어지는 자두를 최대로 먹어라' 입니다.


매번 움직여서 받을 수 있다면 떨어지는 자두 수가 최대이겠지만..

안타깝게도 움직임이 제한되어있습니다. (W)


그래서 저는 X초에 Y번 움직이고 먹은 최대의 자두 수라고 정의를 했습니다.

변수가 두개이니 2차원 DP가 될 것입니다.


1
2
3
4
#define MAX_SIZE 1010
#define MAX_MOVE 31
int data[MAX_SIZE];
int dp[MAX_SIZE][MAX_MOVE];
cs


이 문제를 푸신 분들을 보면 3차원 DP로 정의하는 경우가 있는데..

그 정의는 X초에 Y번 움직이고 Z의 위치에 있을 때 먹은 최대의 자두 수 입니다.

물론 이렇게 풀어도 되지만..


저는 Y번 움직일 때 사람(자두)의 위치를 알 수 있습니다.

1번 나무에서 시작하므로 한번 움직였다면 2번 나무

두번 움직였다면 1번 나무

세번 움직였다면 2번 나무

.

.

.


n번 움직였다면 n % 2가 짝수일 때 1번 나무, 홀수일 때 2번 나무입니다.

이 문제의 핵심이죠~


아래의 코드는 점화식입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
    for(int i = 1; i <= T; i++)
    {
        if(data[i] == 1) dp[i][0] = dp[i - 1][0] + 1;
        else dp[i][0] = dp[i - 1][0];
 
        for(int  j = 1; j <= i && j <= W; j++)
        {
            if(data[i] == 1 && j % 2 == 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else if(data[i] == 2 && j % 2 == 1) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
 
            ret = max(ret, dp[i][j]);
        }
    }
cs


i초에 떨어지는 자두가 1이고 움직인 수가 짝수라면
혹은 i초에 떨어지는 자두가 2이고 움직인 수가 홀수라면..
혹은 i초에 떨어지는 자두가 1인데 나는 2에 있거나.. 2인데 나는 1에 있거나 하면 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
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
 
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define MAX_SIZE 1010
#define MAX_MOVE 31
 
using namespace std;
 
typedef pair<int, int> p;
 
int data[MAX_SIZE];
int dp[MAX_SIZE][MAX_MOVE];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int main()
{
    int T, W;
    scanf("%d %d", &T, &W);
 
    for(int i = 1; i <= T; i++) scanf("%d", data + i);
 
    int ret = 0;
 
    for(int i = 1; i <= T; i++)
    {
        if(data[i] == 1) dp[i][0] = dp[i - 1][0] + 1;
        else dp[i][0] = dp[i - 1][0];
 
        for(int  j = 1; j <= i && j <= W; j++)
        {
            if(data[i] == 1 && j % 2 == 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else if(data[i] == 2 && j % 2 == 1) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
 
            ret = max(ret, dp[i][j]);
        }
    }
 
    printf("%d\n", ret);
    return 0;
}
cs


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

[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20
[2294] 동전 2  (0) 2017.04.19
[2293] 동전 1  (4) 2017.04.19
[1727] 커플 만들기  (0) 2017.04.05

+ Recent posts

티스토리툴바