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

 

N명의 친구가 방에 방문할 예정이고, 친구가 있는 시간에는 난로가 켜져 있어야 합니다.

난로는 K번까지 켤 수 있으며, 난로가 켜져있는 최소 시간을 구해야합니다.

 

이 문제는 인접한 시간의 간격을 이용하여 그리디하게 문제를 풀 수 있습니다.

우선 N명의 친구가 방문할때는 난로가 켜져있어야 하기 때문에 N번의 난로를 모두 켜주도록 합니다.

여기서 난로가 켜져있는 시간은 N이고, N번 난로를 켠 상태입니다.

 

난로는 최대 K번까지만 켤 수 있으므로 "친구가 나간 시간 ~ 다른 친구가 들어온 시간"의 간격 동안에는 난로가 추가로 켜져있어야 합니다.

즉 list[i] - (list[i - 1] + 1) 시간 동안에는 추가로 난로가 켜져 있어야 합니다.

그렇다면 이 시간들을 작은 값부터 더해준다면 답을 구할 수 있습니다.

 

저는 그 시간들을 벡터에 넣어줬고, 벡터를 오름차순으로 정렬했습니다.

이후에는 cnt = K가 될때까지 벡터에 있는 시간들을 추가로 더해주도록 합니다.

 

 

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
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;
 
vector<int> v;
int list[MAX];
int N, K;
 
void func() {
    for (int i = 1; i < N; i++) {
        v.push_back(list[i] - (list[i - 1+ 1));
    }
    sort(v.begin(), v.end());
 
    int ret = N;
    int cnt = N;
    int idx = 0;
    while (cnt > K) {
        ret += v[idx++];
        cnt--;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 2513 통학버스  (0) 2024.07.14
boj 1437 수 분해  (0) 2024.07.12
boj 23559 밥  (0) 2024.07.11
boj 2140 지뢰찾기  (0) 2024.07.10
boj 1132 합  (0) 2024.07.08

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

 

숫자 N을 0이 아닌 정수의 합으로 나타낼 수 있으며, 그 수들의 곱의 최댓값을 구하는 문제입니다.

우선 그 합을 이루는 정수는 N이 커질수록 답이 커질수밖에 없습니다.

그 기준은 5가 되겠습니다.

5 = 2 + 3이며, 2 * 3 = 6 > 5이기 때문이죠.

5보다 작은 수는 그 수 자체를 곱하는게 더 크다고 할 수 있습니다.

 

그렇다면 문제를 쉽게 해결할 수 있습니다.

N을 5보다 작은 어떤 수로 계속 빼면 답을 구할 수 있습니다.

그 수는 3이나 4가 될 수 있을텐데, 6 = 2 + 2 + 2 = 3 + 3의 경우를 보시면 3이 최대한 많이 들어가는 수가 크다는 것을 알 수 있습니다.

다른 수로 직접 구해보셔도 4보다는 3으로 나누는 것이 제일 이득입니다.

따라서 N < 5가 되기 전까지는 3을 계속 빼주도록 하고, 남은 5 미만의 N을 곱해주시면 됩니다.

 

 

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
#include <iostream>
#define MOD 10007
using namespace std;
 
int N;
 
void func() {
    int ret = 1;
    while (N >= 5) {
        N -= 3;
        ret = (ret * 3) % MOD;
    }
    cout << (ret * N) % MOD << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 2513 통학버스  (0) 2024.07.14
boj 15553 난로  (0) 2024.07.13
boj 23559 밥  (0) 2024.07.11
boj 2140 지뢰찾기  (0) 2024.07.10
boj 1132 합  (0) 2024.07.08

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

 

A 메뉴를 선택할 수 있다면 선택하는 것이 좋습니다.

하지만 보유중인 금액은 한계가 있으므로 최적의 선택을 하기 위해 A, B 메뉴 맛의 차이가 큰 것을 선택하는 것이 좋습니다.

그래서 A - B를 기준으로 내림차순 정렬해줍니다.

 

그다음 0원으로 시작하여 A를 선택하게 되면 나중에 금액이 부족해질 수 있습니다.

따라서 시작 금액을 모든 메뉴를 B로 선택하는 N * 1000으로 세팅할 수 있습니다.

그렇게 한다면 A 메뉴를 선택했을 때 4000원만 추가해주면 되고, 금액이 부족해지면 추가금액 없이 B를 선택해줄 수 있습니다.

 

 

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 <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef pair<intint> pii;
 
pii list[MAX];
int N, X;
 
bool cmp(pii a, pii b) {
    return a.first - a.second > b.first - b.second;
}
 
void func() {
    sort(list, list + N, cmp);
 
    int ret = 0;
    int cost = N * 1000;
    for (int i = 0; i < N; i++) {
        if (cost + 4000 <= X && list[i].first > list[i].second) {
            cost += 4000;
            ret += list[i].first;
        }
        else ret += list[i].second;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> X;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 15553 난로  (0) 2024.07.13
boj 1437 수 분해  (0) 2024.07.12
boj 2140 지뢰찾기  (0) 2024.07.10
boj 1132 합  (0) 2024.07.08
boj 25381 ABBC  (0) 2024.07.07

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

 

보드의 테두리에 숫자가 있고, 닫혀있는 칸들 중 지뢰가 최대 몇개 묻혀져 있는지 구하는 문제입니다.

지뢰의 최대 수를 구하면 되기 때문에 닫혀있는 칸들 중 지뢰가 아닌 칸은 숫자라고 생각하시면 되겠습니다.

 

우선 지뢰가 있으려면 주변에 0이 없어야 합니다.

8방향 탐색으로 0이 있는지 확인하시고, 0이 없다면 지뢰를 묻어주도록 합니다.

지뢰를 묻은 칸은 -1으로 변경해주고, 주변 8방향에 있는 숫자 칸들은 모두 -1을 해줍니다.

-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
56
57
58
59
60
#include <iostream>
#define MAX 101
using namespace std;
 
char list[MAX][MAX];
int direct[8][2= { {1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1} };
int N;
 
void eraseNum(int x, int y) {
    for (int d = 0; d < 8; d++) {
        int nx = x + direct[d][0];
        int ny = y + direct[d][1];
        if (list[nx][ny] == -1 || list[nx][ny] == '#'continue;
        list[nx][ny] -= 1;
    }
}
 
void func() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (list[i][j] != '#'continue;
 
            bool flag = true;
            for (int d = 0; d < 8; d++) {
                int nx = i + direct[d][0];
                int ny = j + direct[d][1];
 
                if (list[nx][ny] == '0') {
                    flag = false;
                    break;
                }
            }
 
            if (flag) {
                ret++;
                list[i][j] = -1;
                eraseNum(i, j);
            }
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 1437 수 분해  (0) 2024.07.12
boj 23559 밥  (0) 2024.07.11
boj 1132 합  (0) 2024.07.08
boj 25381 ABBC  (0) 2024.07.07
boj 28325 호숫가의 개미굴  (0) 2024.07.06

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

 

https://whyeskang.com/29

 

boj 1339 단어 수학

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있

whyeskang.com

이 문제와 접근 방식이 같습니다.

다만 다른점은 위 문제와 다르게 첫 글자에 0이 올 수 없다는 것을 추가로 고려해야 합니다.

 

알파벳의 각 자릿수의 합은 문자열을 뒤에서부터 1, 10, 100, 1000 ... 이렇게 10씩 곱한 값을 더해주시면 됩니다.

그 후에 첫번째에 오는 알파벳을 체크했다가 0을 부여 받을 알파벳을 선정하도록 합니다.

선정 로직은 zeroChk가 false인 알파벳들 중 가장 작은 자릿수를 가진 알파벳에 0을 넣으면 됩니다.

 

나머지는 각 자릿수의 합 배열 (num)을 내림차순으로 정렬하여 큰 수부터 값을 더해주시면 되겠습니다.

알파벳이 10개 미만으로 사용되었더라도 나머지 알파벳은 zeroChk가 false이고, 자릿수가 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
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
#include <iostream>
#include <string>
#include <algorithm>
#define MAX_N 51
#define MAX_M 10
using namespace std;
typedef long long ll;
 
string list[MAX_N];
ll num[MAX_M];
bool zeroChk[MAX_M];
int N;
 
void init() {
    int zIdx = -1;
    for (int i = 0; i < N; i++) {
        int len = list[i].size();
        ll d = 1LL;
        for (int j = len - 1; j >= 0; j--) {
            num[list[i][j] - 'A'+= d;
            d *= 10LL;
        }
 
        zeroChk[list[i][0- 'A'= true;
    }
 
    for (int i = 0; i < MAX_M; i++) {
        if (zeroChk[i]) continue;
        if (zIdx == -1 || num[zIdx] > num[i]) zIdx = i;
    }
    num[zIdx] = 0;
}
 
void func() {
    init();
 
    sort(num, num + MAX_M, [](ll a, ll b) {
        return a > b;
    });
 
    ll ret = 0;
    ll n = 9;
    for (int i = 0; i < MAX_M; i++) {
        ret += (n * num[i]);
        n--;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 23559 밥  (0) 2024.07.11
boj 2140 지뢰찾기  (0) 2024.07.10
boj 25381 ABBC  (0) 2024.07.07
boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05

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

 

- A와 그 뒤에 있는 B를 지운다.

- B와 그 뒤에 있는 C를 지운다.

문자열을 지울 수 있는 두 가지 방법입니다.

여기서 B가 중복되었다는 것을 이용할 수 있습니다.

 

1. A보다 뒤에 있는 B를 지울때 최대한 뒤에 있는 B를 지우거나

2. C보다 앞에 있는 B를 지울때 최대한 앞에 있는 B를 지우거나

둘 중 하나를 먼저 진행하시면 이 문제를 해결할 수 있습니다.

 

저는 2번 방법으로 문제를 풀었습니다.

문자열을 한 번 순회하면서 B를 만나면 queue에 넣고, C를 만나면 queue에 있는 B를 하나 제거합니다.

이때 queue에는 B의 인덱스를 넣었고, 가장 앞의 인덱스가 먼저 제거됩니다.

 

그렇게 BC 를 모두 지웠으니 이제 AB를 지우도록 합니다.

BC 조합을 먼저 지웠기 때문에 queue에 들어있는 B를 그냥 지워주시면 됩니다.

여기서 주의할건 현재 순회중인 인덱스보다 낮은 인덱스가 queue에 있다면 먼저 제거해야 합니다.

 

 

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 <iostream>
#include <queue>
#include <string>
using namespace std;
 
queue<int> q;
string str;
int len;
 
void func() {
    int ret = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == 'B') q.push(i);
        else if (str[i] == 'C') {
            if (q.empty()) continue;
            q.pop();
            ret++;
        }
    }
 
    for (int i = 0; i < len && !q.empty(); i++) {
        while (!q.empty() && q.front() < i) q.pop();
        if (str[i] == 'A') {
            if (q.empty()) continue;
            q.pop();
            ret++;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> str;
    len = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 2140 지뢰찾기  (0) 2024.07.10
boj 1132 합  (0) 2024.07.08
boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03

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

 

1 ~ N번 방은 서로 원형으로 연결되어 있으며, 각 방에는 Ci개의 쪽방이 있을 수 있습니다.

통로로 직접 연결되어 있는 두 방에는 하나의 개미만 들어갈 수 있으며, 개미굴에 살고있는 개미의 최대 수를 구하는 문제입니다.

 

문제의 카테고리가 dp와 그리디가 있었지만 저는 그리디로 해결했습니다.

우선 쪽방이 있다면 무조건 들어가는 것이 이득입니다.

쪽방은 i번 방의 바로 아래에 있는 자식 노드기 때문에 쪽방의 갯수를 세어주도록 합니다.

 

그 다음은 쪽방이 없는 나머지 방을 세어줍니다.

나머지 방에는 연속된 방으로 세어주시고, (연속된 방의 갯수 (cnt) + 1) / 2으로 구할 수 있습니다.

 

그것들을 정답에 더해주시면 되는데 마지막으로 생각할게 개미굴은 원형으로 되어있기 때문에 1번과 N번 방이 서로 연결되어 있습니다.

순회를 1번 방부터 했기 때문에 만약 1번과 N번 방 둘다 쪽방이 없다면 연속된 방의 갯수들을 합쳐줘야 합니다. (cnt + tmp)

그걸 위해서 처음에 1번 방부터 isFirst 변수를 추가하여 처음 연속된 빈방의 갯수를 tmp에 저장해두었습니다.

 

 

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
#include <iostream>
#define MAX 250001
using namespace std;
typedef long long ll;
 
ll list[MAX];
bool flag;
int N;
 
void func() {
    if (!flag) {
        cout << (N >> 1<< '\n';
        return;
    }
 
    ll ret = 0;
    ll cnt = 0;
    ll tmp = 0;
    bool isFirst = true;
    for (int i = 0; i < N; i++) {        
        if (!list[i]) cnt++;
        else {
            if (isFirst) tmp = cnt;
            ret += list[i];
            isFirst = false;
            ret += ((cnt + 1LL) >> 1);
            cnt = 0;
        }
    }
 
    if (!list[0&& !list[N - 1]) {
        ret -= ((tmp + 1LL) >> 1);
        ret += ((tmp + cnt + 1LL) >> 1);
    }
    else ret += ((cnt + 1LL) >> 1);
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        flag |= list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 1132 합  (0) 2024.07.08
boj 25381 ABBC  (0) 2024.07.07
boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02

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

 

소는 A ~ B 시간 사이에만 이동할 수 있고, 닭은 T 시간에만 도움을 줄 수 있습니다.

즉 A <= T <= B 가 되어야 닭이 소를 도와줄 수 있습니다.

 

구현은 간단합니다.

가장 빠르게 도움을 줄 수 있는 닭을 찾기 위해 닭은 오름차순으로 정렬합니다.

그리고 소는 끝시간 기준 오름차순으로 정렬합니다.

이후에는 소 한마리씩 순회하여 도움을 받을 적절한 닭을 찾아주시면 됩니다.

 

범위가 각각 2만이기 때문에 TLE가 나오지 않을까 생각했지만 N * M으로도 풀리는 문제였습니다.

아마 중간에 적절한 답을 찾으면 break를 해주면서 시간이 어느정도 단축되는 것으로 보입니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 20001
using namespace std;
typedef pair<intint> pii;
 
int list[MAX];
pii cow[MAX];
int N, M;
 
void func() {
    sort(list, list + N);
    sort(cow, cow + M, [](pii a, pii b) {
        return a.second < b.second;
    });
 
    int ret = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (list[j] == -1continue;
            if (cow[i].first > list[j] || list[j] > cow[i].second) continue;
 
            ret++;
            list[j] = -1;
            break;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
 
    for (int i = 0; i < M; i++) {
        cin >> cow[i].first >> cow[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 25381 ABBC  (0) 2024.07.07
boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16

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

 

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 ...

위 동전들을 적절히 사용하여 N을 만들기 위한 최소 갯수를 구하는 문제입니다.

 

동전들을 3개씩 끊어본다면

(1, 10, 25)

(1, 10, 25) * 100

(1, 10, 25) * 100 * 100

(1, 10, 25) * 100 * 100 * 100

이런식으로 규칙이 된다는 것을 알 수 있습니다.

그러면 굳이 문제에서 요구하는 큰 범위까지 갈 필요 없이 100 단위로 끊어서 접근한다면 간단하게 해결할 수 있습니다.

 

같은 금액에서의 답은 똑같기 때문에 dp를 사용했습니다.

그리고 dp 배열을 초기화할 필요도 없습니다.

(1, 10, 25) 으로 99원을 만들든, (100, 1000, 2500) 으로 9900원을 만들든 똑같은 결과가 나오기 때문입니다.

여기까지 오셨다면 구현은 간단합니다.

 

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 101
using namespace std;
typedef long long ll;
 
int dp[MAX];
int list[3= { 1,10,25 };
ll N;
 
int solve(int n) {
    if (!n) return 0;
 
    int& ret = dp[n];
    if (ret != -1return ret;
 
    ret = 1e9;
    for (int i = 0; i < 3; i++) {
        if (n < list[i]) continue;
 
        ret = min(ret, solve(n - list[i]) + 1);
    }
    return ret;
}
 
void func() {
    memset(dp, -1sizeof(dp));
    
    int ret = 0;
    while (N) {
        ret += solve(N % 100LL);
        N /= 100LL;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
cs

'algorithm > dp' 카테고리의 다른 글

boj 30461 낚시  (0) 2024.07.28
boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28

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

 

문제를 보자마자 6068번 시간 관리하기 문제랑 같다는 것을 느꼈습니다.

마감 시간(Si)과 일을 하는데 걸리는 시간(Ti)이 주어지고, 언제부터 시작하면 일을 끝낼 수 있는지 구해야 합니다.

마감 시간 기준 내림차순으로 정렬하여 뒤에서부터 탐색한다면 쉽게 해결할 수 있습니다.

저는 혹시 몰라서 Si가 같다면 Ti 기준으로도 정렬을 했지만 생각해보니 그럴 필요는 없어보입니다.

 

시간을 최대로 세팅을 먼저 하고, 내려가면서 Ti를 빼주시면 되겠습니다.

도중에 현재 작업의 Si보다 t가 더 크다면 Si로 현재 시간을 조정해주시면서 진행해주시면 됩니다.

 

 

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 <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
typedef pair<intint> pii;
 
pii list[MAX];
int N;
 
bool cmp(pii a, pii b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
void func() {
    sort(list, list + N, cmp);
 
    int t = 1e9;
    for (int i = 0; i < N; i++) {
        t = min(t, list[i].second);
        t -= list[i].first;
 
        if (t < 0) {
            cout << "-1\n";
            return;
        }
    }
 
    cout << t << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 28325 호숫가의 개미굴  (0) 2024.07.06
boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16

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

 

다이아 문제중에 해볼만한 문제로 가져와봤습니다.

 

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i + 1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i + 1)번 공장, (i + 2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N - 2). 이 경우 비용은 7원이 든다.

우선 라면을 구매할 수 있는 방법은 이렇게 3가지입니다.

 

i번째 공장에서는 남아있는 모든 라면을 구매하는게 맞겠고,

i + 1, i + 2번째 공장의 라면을 가능하면 추가로 구매하는게 더 좋습니다.

제가 구현한 방식은 i번째 라면은 개당 3원씩 모두 구매하고, i + 1, i + 2번째 라면을 구매할때마다 2원을 추가하는 방식으로 구현했습니다.

 

하지만 i ~ i + 2 범위 내에 가능한 모든 라면을 구매한다면 반례가 존재합니다.

4
1 2 1 1

여기서 가능한대로 모든 라면을 구매한다고 했을 때 1 ~ 3번째 공장에서 라면을 구매했을 것입니다. (소모한 금액: 7)

0 1 0 1

그러면 남은 라면은 이렇게 될 것이고, 남은 공장에서 하나씩 구매한다면 7 + 3 + 3 = 13의 금액이 필요합니다.

 

 

하지만 처음에 3번 공장에서 구매하지 않는다면

0 1 1 1

1, 2번째 공장에서만 라면을 구입하고, (소모한 금액: 5)

나머지 2 ~ 4번째 공장에서 라면을 구입한다면 5 + 7 = 12의 금액이 필요하여 이게 최소가 됩니다.

 

따라서 하나더 고려해야할 부분은 최초 필요한 갯수가 list[i + 1] > list[i + 2] 이라면

"i + 1번째 공장에서 남긴 수만큼 i + 2번째 공장에서도 남겨야 한다"가 됩니다.

물론 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
#include <iostream>
#include <algorithm>
#define MAX 10010
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        if (!list[i]) continue;
        int cnt = list[i];
        list[i] = 0;
        ret += (3 * cnt);
 
        if (i + 1 >= N) continue;
        cnt = min(cnt, list[i + 1]);
        list[i + 1-= cnt;
        ret += (2 * cnt);
 
        if (i + 2 >= N) continue;
        if (cnt + list[i + 1> list[i + 2]) {
            cnt = min(cnt, max(0, list[i + 2- list[i + 1]));
        }
        list[i + 2-= cnt;
        ret += (2 * cnt);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Greedy' 카테고리의 다른 글

boj 14464 소가 길을 건너간 이유 4  (0) 2024.07.05
boj 1263 시간 관리  (0) 2024.07.03
boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30

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

 

간단한 dp 문제입니다.

문제가 요구하는 육각수들의 수를 미리 구한 다음 N을 만들기 위해 필요한 육각수의 갯수를 구하여 해결할 수 있습니다.

 

육각수의 수는

1 * 1

2 * 3

3 * 5

4 * 7

5 * 9

이렇게 규칙을 찾을 수 있고, An = n * (2n - 1) 으로 구할 수 있습니다.

 

dp[i] = i를 만들기 위해 필요한 육각수의 최소 갯수

인덱스가 갯수이므로 dp[i] = dp[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
#include <iostream>
#define MAX_N 1000001
#define MAX_M 710
using namespace std;
 
int list[MAX_M];
int dp[MAX_N];
int N;
 
void init() {
    for (int i = 1; i < MAX_M; i++) {
        list[i] = i * ((i << 1- 1);
    }
}
 
void func() {
    init();
 
    dp[1= 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = 1e9;
        for (int j = 1; j < MAX_M; j++) {
            if (i < list[j]) break;
            dp[i] = min(dp[i], dp[i - list[j]] + 1);
        }
    }
 
    cout << dp[N] << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > dp' 카테고리의 다른 글

boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27

+ Recent posts