1744. 수 묶기


문제

길이가 N인 수열이 주어졋을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 어떤 인접한 원소끼리를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때, 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

수를 적절히 묶어 그 합이 최대값을 출력한다. 정답은 항상 231보다 작다.

예제 입력 

4
-1
2
1
3

예제 출력 

6



1. 접근


그리디 알고리즘. 여러 수들을 묶거나 더해서 가장 큰 수를 만들려면 가장 큰 두 수(양수) 나 가장 작은 수 (음수)들을 묶어야 한다.



2. 풀이


0 < a < b < c < d 인 수 네 개를 규칙에 따라 가장 큰 합을 만들려면 어떻게 해야 할까?

1) a * b + c * d

2) a * c + b * d

3) a * d + b * c


직관적으로 1번이 가장 큰걸 알고 있다.

1번과 2번을 빼면 a * (b - c) > d * (b - c) 이므로 1번이 더 크다.

1번과 3번을 빼면 a * (b - d) > c * (b - d) 이므로 1번이 더 크다. 


음수에 양수를 곱해봤자 전체 합은 작아만지므로 음수는 가능한 음수와만 곱해야함이 자명하다.


따라서 음수와 양수를 따로 생각해서 가장 큰 수 두 개씩 묶어나가면 되겠다.


다만 1과 0은 예외적인 수인데, 0은 음수를 묶어나가고 남은 짜투리에 곱해서 0으로 만드는데 사용하고,

1은 곱해봤자 총 합을 늘리는데 도움이 되지 않으므로 1은 더하는데만 사용하면 되겠다.



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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
 
int n, i, tmp, z, one, as, bs, sum;
priority_queue<int, vector<int>, greater<int>> a;
priority_queue<int, vector<int>, less<int>> b;
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        if (tmp == 1)
            one++;
        else if(tmp > 0)
            a.push(tmp);
        else if (tmp < 0)
            b.push(tmp);
        else
            z++;
    }
    if (a.size() % 2 == 1)
        a.push(1);
    if (b.size() % 2 == 1)
        z == 0 ? b.push(1) : b.push(0);
 
    as = a.size() / 2;
    bs = b.size() / 2;
    for (i = 0; i < as; ++i) {
        tmp = a.top();
        a.pop();
        sum += a.top()*tmp;
        a.pop();
    }
    for (i = 0; i < bs; ++i) {
        tmp = b.top();
        b.pop();
        sum += b.top()*tmp;
        b.pop();
    }
    printf("%d", sum + one);
    return 0;
}
cs


양수들의 큐와 음수들의 큐를 처리한 나머지 짜투리를 예외처리하기 귀찮으므로 추가로 1이나 0을 넣어주는 센스

'알고리즘 > Greedy 그리디' 카테고리의 다른 글

백준) 1931 회의실배정  (0) 2017.07.25
백준) 1946 신입 사원  (0) 2017.07.25
백준) 4796 캠핑  (0) 2017.07.23
백준) 11047 동전 0  (0) 2017.07.23
그리디 알고리즘 도입  (0) 2017.07.23

4796. 캠핑


문제

등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 써있었다.

캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.

강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 몇 일동안 사용할 수 있을까?

강산이는 조금 더 일반화해서 문제를 풀려고 한다. 

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 몇 일동안 사용할 수 있을까? (1 < L < P < V)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스에 대해서, 강산이가 캠핑장을 최대 몇 일동안 사용할 수 있는지 예제 출력처럼 출력한다.

예제 입력 

5 8 20
5 8 17
0 0 0

예제 출력 

Case 1: 14
Case 2: 11



1. 접근


그리디 알고리즘을 적용할 수 있다.


V일을 P일 단위로 나누고, 매 단위마다 어떤 날부터 연속으로 L일 만큼 사용해야 최대한 많이 사용할 수 있는지 묻는 문제다.



2. 풀이


거창하게 그리디로 분석하지 않아도, 직관적으로 생각해보면


V일을 P일 단위로 나누고 남은 짜투리 일은 P일 보다 작을 것이므로, 전부 이용할 수 있다.

또한 P일 단위들은 어떤 날부터 시작하든지 L일만큼 자유롭게 사용할 수 있다.

(0일 부터 L-P일 전까지만 시작하면 최대 L일을 연속으로 쓸 수 있다.)


따라서 (V / P) * L 일 + 짜투리 일 만큼이 정답이 될 것이다.


탐욕적으로 선택해 나가는 방법을 생각해보자면, V일을 처음부터 P일로 연속적으로 나눠가는 것이 당연히 최적해이다.

처음부터 나누지 않으면 당연히 손실이 발생한다. 나머지 짜투리 또한 당연히 첫날부터 최대한 이용(L일 까지)하는 것이 이득이다.


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
using namespace std;
 
int l, p, v, i;
 
int main() {
    while (1) {
        scanf("%d %d %d", &l, &p, &v);
        if (!l && !p && !v)
            return 0;
 
        i++;
        int tmp = v % p;
        if (tmp < l)
            printf("Case %d: %d\n", i, v / p * l + tmp);
        else
            printf("Case %d: %d\n", i, v / p * l + l);
    }
}
cs


'알고리즘 > Greedy 그리디' 카테고리의 다른 글

백준) 1931 회의실배정  (0) 2017.07.25
백준) 1946 신입 사원  (0) 2017.07.25
백준) 1744 수 묶기  (0) 2017.07.24
백준) 11047 동전 0  (0) 2017.07.23
그리디 알고리즘 도입  (0) 2017.07.23

11047. 동전 0


문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다. 이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)


출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최소값을 출력한다.


1. 접근


그리디 알고리즘. 


2. 풀이


가장 큰 액수의 동전들을 최대한으로 써가면서 K원을 만든다.


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
using namespace std;
 
int n, k, i;
int coin[10];
 
int main() {
    scanf("%d %d", &n, &k);
    for (i = 0; i < n; ++i)
        scanf("%d", &coin[i]);
 
    int cnt = 0;
    for (i = n - 1; i >= 0; --i) {
        cnt += k / coin[i];
        k %= coin[i];
    }
    printf("%d", cnt);
    return 0;
}
cs


'알고리즘 > Greedy 그리디' 카테고리의 다른 글

백준) 1931 회의실배정  (0) 2017.07.25
백준) 1946 신입 사원  (0) 2017.07.25
백준) 1744 수 묶기  (0) 2017.07.24
백준) 4796 캠핑  (0) 2017.07.23
그리디 알고리즘 도입  (0) 2017.07.23

+ Recent posts

티스토리툴바