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

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


이분 탐색을 재귀로 구현해보았습니다!

여기서 중요한 것은 mid와 left right를 롱롱형으로 처리한다는 점입니다.

right 초기값을 signed int의 최대값으로 설정했기 때문에 1 + right를 할 경우에

int범위를 벗어나게 됩니다. 그러므로 롱롱형으로 처리를 했습니다.


이 문제도 마찬가지로 무엇을 이분탐색으로 탐색할 것인가??에 대해서 고민하면 쉽게 풀 수 있습니다.

여기서 탐색할 것은 랜선의 길이입니다. 각 랜선에서 몇미터짜리의 랜선으로 자를 것인가!
처음에 최대값부터 시작해서... 이분탐색을 합니다!

임의의 값으로 랜선을 잘랐을 때 랜선의 수가 요구하는 개수보다 많아지면 더 길게!

반대의 경우는 짧게 탐색을 합니다.

조심해야할 점은 문제에서 최대 길이를 요구했으므로

어떤 길이로 잘랐을때 랜선의 개수 N을 만족하더라도 더 긴 길이의 랜선으로 만들어보아야합니다.

예를들어 200으로 잘랐는데도 랜선 N개를 만족할 수도 있고 201도 만족한다면 답은 201이 되어야한다는 말입니다.


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
#include <cstdio>
#define MAX_SIZE 10000
#define INF 0x7fffffff
#define ll long long
int data[MAX_SIZE];
int k, n;
int ret;
 
int binary_search(int key, ll left, ll right)
{
    if(left > right) return -1;
 
    ll mid = (left + right) / 2;
 
    int cnt = 0;
    for(int i = 0; i < k; i++) cnt += data[i] / mid;
 
 
    if(cnt >= key)
    {
        ret = mid > ret ? mid : ret;
        return binary_search(key, mid + 1, right);
    }
    else if(cnt < key) return binary_search(key, left, mid - 1);
 
}
 
int main()
{
 
    scanf("%d %d", &k, &n);
 
    for(int i = 0; i < k; i++) scanf("%d", data + i);
 
    binary_search(n, 1, INF);
 
    printf("%d", ret);
 
    return 0;
}
 
cs


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

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

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

이 문제는 저는 개인적으로 꽤 어려웠는데요....

이분 탐색으로 풀 수 있는 문제입니다..

파라메트릭 서치(?)라고.. K번째 수와 마찬가지로 이분 탐색의 응용인 문제인데

집의 수와 공유기의 수 그리고 집의 좌표를 줍니다.


최대한 넓게 넓게 설치해서 인풋으로 요구하는 공유기의 수를 만들어야 하는데..

여기서 어떻게 이분탐색을 하느냐에 대해서 엄청나게 고민했습니다.


결론부터 말하자면! 우리는 거리를 가지고 이분탐색을 해야합니다.


예를 들어 거리를 10으로 첫 시작을 했다면 10간격으로 설치를 해보고 공유기가 더 많이 필요하면 간격을 늘리고

공유기가 덜 설치되었으면 거리를 줄이는 방식으로 이분탐색을 진행하면 됩니다.


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 <cstdio>
#include <algorithm>
#define MAX_SIZE 200000
 
int pos[MAX_SIZE];
 
int main()
{
    int n, c;
    scanf("%d %d", &n, &c);
 
    for(int i = 0; i < n; i++) scanf("%d", pos + i);
 
    std::sort(pos, pos + n);
 
    int left = 1, right = pos[n - 1] - pos[0];
    int ret;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int cnt = 1;
        int start = pos[0];
 
        for(int i = 1; i < n; i++)
        {
            if(pos[i] - start >= mid)
            {
                cnt++;
                start = pos[i];
            }
        }
 
        if(cnt >= c)
        {
            ret = mid;
            left = mid + 1;
        }
        else right = mid - 1;
 
    }
 
    printf("%d\n", ret);
 
 
    return 0;
}
 
cs


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

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

그냥 문제에 주어진 조건대로 움직이기만 하면 끝나는 문제입니다.

말이 좀 난해하긴한데... 디버깅하면서 따라가니 이해가 가더라구요!

그림 그려보시면 편하실 것 같습니다.


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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 51
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
int sx, sy, sd;
 
//process
int max_value;
int dx[4] = { -1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
 
 
void input()
{
    scanf("%d %d", &m, &n);
    scanf("%d %d %d", &sx, &sy, &sd);
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
}
 
int turn(int now, int next)
{
    if(next == 0)//next == 0은 왼쪾으로 턴
    {
        if(now == 0) return 3;
        else if(now == 1) return 0;
        else if(now == 2) return 1;
        else return 2;
    }
    else return (now + 2) % 4;//0->2,2->0,1->3,3->1
}
 
 
void print()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            printf("%d ", map[i][j]);
        }
        puts("");
    }
    puts("");
}
 
void process()
{
    int x = sx;
    int y = sy;
    int d = sd;
    int cnt = 0;
 
    int ret = 1;
    map[x][y] = 2;
 
    int nx;
    int ny;
 
    while(1)
    {
        if(cnt == 4)
        {
            d = turn(d, 1);
            nx = x + dx[d];
            ny = y + dy[d];
 
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] == 1) break;
 
            x = nx;
            y = ny;
            d = turn(d, 1);
            cnt = 0;
            continue;
        }
 
        d = turn(d, 0);
        nx = x + dx[d];
        ny = y + dy[d];
 
        cnt++;
 
 
        if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0) continue;
 
        x = nx;
        y = ny;
 
        map[x][y] = 2; // 청소함!
 
        ret++;
        cnt = 0;
    }
 
    printf("%d\n", ret);
}
 
int main()
{
    input();
    process();
 
    return 0;
}
 
cs


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

[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23
[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17

+ Recent posts

티스토리툴바