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/16120

 

16120번: PPAP

첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

www.acmicpc.net

P는 PPAP 문자열이며, P를 PPAP로 바꾼 문자열 역시 PPAP 문자열입니다.

이 조건과 문자열 주어졌을 때 PPAP 문자열인지 판별하는 문제입니다.

 

우선 문자열의 처음부터 순회를 합니다.

해당 위치의 문자가

'P'이면 cnt를 1 증가합니다.

'A'이면 cnt가 2 이상이고, 다음 문자가 'P'이면 PPAP문자열이므로 PPAP를 P로 변경합니다.

실제 로직으로는 cnt를 1 감소하고, 다음 인덱스가 P인것을 확인했으니 인덱스도 1 증가합니다.

만약 'A'일때 cnt가 2보다 작거나, 마지막 인덱스이거나, 다음 문자가 'P'가 아니면 NP를 출력합니다.

 

순회가 끝났을때 남는 문자열은 P여야하므로 cnt가 1일때만 PPAP를 출력, 아니면 NP를 출력합니다.

 

 

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 <iostream>
#include <string>
using namespace std;
 
string str;
int N;
 
void func() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (str[i] == 'P') cnt++;
        else {
            if (cnt >= 2 && i < N - 1 && str[i + 1] == 'P') {
                cnt--;
                i++;
            }
            else {
                cout << "NP\n";
                return;
            }
        }
    }
 
    if (cnt == 1) cout << "PPAP\n";
    else cout << "NP\n";
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 1263 시간 관리  (0) 2024.07.03
boj 18185 라면 사기 (Small)  (0) 2024.07.02
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22

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

 

2262번: 토너먼트 만들기

월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러

www.acmicpc.net

주어지는 랭킹은 중복이 없으며, 랭킹이 높은 사람 (숫자가 낮은 사람)이 무조건 이깁니다.

문제에서 요구하는 것은 이 토너먼트에서 각 경기에 임하는 선수들의 랭킹의 차이의 합이 최소가 되도록 대진을 구성해야합니다.

 

랭킹이 낮을수록 (숫자가 클수록) 랭킹의 차이의 합이 커지므로 랭킹이 낮은 선수는 빠르게 경기를 하는 것이 이득입니다.

따라서 랭킹이 낮은 선수부터 차례대로 본인의 좌우 선수들 중 랭킹이 낮은 선수와 경기를 하게 만들면 랭킹의 차이의 합이 최소가 됩니다.

 

 

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>
#include <algorithm>
#define MAX 256
using namespace std;
 
int list[MAX];
int N;
 
void func() {
    int ans = 0;
    for (int i = N; i > 1; i--) {
        int j = 0;
        for (; j <= N; j++) {
            if (i == list[j]) break;
        }
 
        ans += (i - max(list[j - 1], list[j + 1]));
 
        for (; j < N; j++) {
            list[j] = list[j + 1];
        }
        N--;
    }
 
    cout << ans << '\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 18185 라면 사기 (Small)  (0) 2024.07.02
boj 16120 PPAP  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16

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

 

13904번: 과제

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

www.acmicpc.net

그리디는 많이 안풀어봐서 어렵네요..

이 문제는 정렬 + 그리디 문제입니다.

 

우선 마감일, 과제 점수를 담은 list배열을

  1. 과제 점수가 높은 순 (내림차순)
  2. 마감일이 적게 남은 순 (오름차순)

으로 정렬합니다.

 

그 다음 과제 점수가 가장 높은 0번 인덱스부터 과제를 진행합니다.

여기서 확인해야할 것은 마감일 안에 과제를 할 수 있는지에 대한 여부입니다.

d일부터 1일까지 visit[d]=true인지 확인해서 해당 일에 과제를 했는지 체크합니다.

과제를 했다면 전날 과제를 했는지 체크하는 방식으로 1일까지 확인합니다.

 

과제를 하지않은 날이 있다면 과제를 진행하고 방문체크 해주면 되고,

d ~ 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 1000
using namespace std;
typedef pair<int, int> pi;
 
pi list[MAX];
bool visit[MAX + 1];
int N;
 
bool cmp(pi a, pi b) {
    if (a.second == b.second) return a.first < b.first;
    else return a.second > b.second;
}
 
void func() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int d = list[i].first;
        for (int j = d; j > 0; j--) {
            if (visit[j]) continue;
            
            visit[j] = true;
            ans += list[i].second;
            break;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    sort(list, list + N, cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 16120 PPAP  (0) 2021.10.16
boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16

www.acmicpc.net/problem/3109

 

3109번: 빵집

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던

www.acmicpc.net

 

파이프는 오른쪽, 대각선 오른쪽 위, 대각선 오른쪽 아래 방향으로 연결할 수 있고,

0번 열에서 M - 1번 열까지 파이프를 이어야하며 최종적으로 파이프라인의 최대 갯수를 출력하는 문제입니다.

 

저는 여기서 앞의 열에서 최대한 앞쪽의 열에 파이프를 연결하면 될것이라는 생각을 하여 백트래킹에 그리디알고리즘을 사용하였습니다.

 

(0, 0) ~ (N - 1, 0)까지 각각 dfs로 끝 열에 도달할 수 있는지 확인해줍니다.

그리디를 사용했기때문에 오른쪽 위 -> 오른쪽 -> 오른쪽 아래 방향 순으로 탐색해줍니다.

끝 열에 도달하면 true를 리턴해주고, 도달하지 못하면 false를 리턴합니다.

true일 경우에만 ans++를 하여 최종 답을 출력합니다.

 

visit배열을 초기화하지 않은 이유는

파이프는 겹칠수 없어서 앞쪽에서 연결한 파이프와 겹칠 수 있기 때문입니다.

만약 최종적으로 연결한 파이프가 아니라고 해도 그 위치에서는 파이프를 연결할 수 없다는 뜻이 되므로 초기화를 하지 않아야합니다.

 

 

[C++]

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 <iostream>
using namespace std;
 
bool visit[10010][510];
char list[10010][510];
int direct[3][2] = { {-1,1},{0,1},{1,1} };
int N, M, ans;
 
bool dfs(int x, int y) {
    visit[x][y] = true;
    if (y == M - 1) return true;
 
    for (int i = 0; i < 3; i++) {
        int nx = x + direct[i][0];
        int ny = y + direct[i][1];
 
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (visit[nx][ny] || list[nx][ny] == 'x') continue;
 
        bool chk = dfs(nx, ny);
        if (chk)
            return true;
    }
 
    return false;
}
 
void func() {
    for (int i = 0; i < N; i++) {
        if (dfs(i, 0)) ans++;
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { -1, 1 }, { 0, 1 }, { 1, 1 } };
    static boolean visit[][];
    static char list[][];
    static int N, M, ans;
 
    static boolean dfs(int x, int y) {
        visit[x][y] = true;
        if (y == M - 1)
            return true;
 
        for (int i = 0; i < 3; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (visit[nx][ny] || list[nx][ny] == 'x')
                continue;
 
            boolean chk = dfs(nx, ny);
            if (chk)
                return true;
        }
 
        return false;
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            if (dfs(i, 0))
                ans++;
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new char[N][];
        visit = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 16922 로마 숫자 만들기  (0) 2021.02.24
boj 1987 알파벳  (0) 2021.02.18
boj 17406 배열 돌리기 4  (0) 2021.02.10
boj 16927 배열 돌리기 2  (0) 2021.02.10
boj 16926 배열 돌리기 1  (0) 2021.02.10

 

www.acmicpc.net/problem/8980

 

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

처음에는 보내는 마을 기준으로 오름차순 정렬하였으나, 반례를 만나고 소스를 갈아엎고 받는 마을 기준으로 오름차순 정렬하였습니다.

 

우선 to배열에는 해당 마을을 지날때 최대용량으로 초기화를 시켜놓았습니다.

다음은 예제로 설명을 하겠습니다.

4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20

N = 4, C = 40, M = 6

택배 정보를 받는 마을 기준으로 정렬하면 이렇게됩니다. to[1] = 40, to[2] = 40, to[3] = 40

1 2 10
1 3 20
2 3 10
1 4 30
2 4 20
3 4 20

이제 1 -> 2로 10만큼을 보냅니다.

도착마을인 2를 제외하고 1 -> 2 경로에 있는 마을의 남은 용량의 최소는 40으로 10보다 큽니다.

그러면 to[1]에서 10만큼 빼줍니다.

(ans = 10)

to[1] = 30, to[2] = 40, to[3] = 40

 

다음 1 -> 3으로 20만큼 보냅니다.

도착마을인 3을 제외하고 1 -> 3 경로에 있는 마을의 남은 용량의 최소는 30으로 20보다 큽니다.

그러면 to[1]와 to[2]에서 20만큼 빼줍니다.

(ans = 10 + 20 = 30)

to[1] = 10, to[2] = 20, to[3] = 40

 

다음 2 -> 3으로 10만큼 보냅니다.

도착마을인 3을 제외하고 2 -> 3 경로에 있는 마을의 남은 용량의 최소는 20으로 10보다 큽니다.

그러면 to[2]에 10만큼 빼줍니다.

(ans = 30 + 10 = 40)

to[1] = 10, to[2] = 10, to[3] = 40

 

다음 1 -> 4로 30만큼 보냅니다.

도착마을인 4를 제외하고 1 -> 4 경로에 있는 마을의 남은 용량의 최소는 10으로 30보다 작습니다.

따라서 남은 용량의 최소만큼인 10만큼 빼줍니다.

(ans = 40 + 10 = 50)

to[1] = 0, to[2] = 0, to[3] = 40

 

다음 2 -> 4로 20만큼 보냅니다.

도착마을인 4를 제외하고 2 -> 4 경로에 있는 마을의 남은 용량의 최소는 0이므로 보낼 수 없습니다.

(ans = 50)

to[1] = 0, to[2] = 0, to[3] = 40

 

다음 3 -> 4로 20만큼 보냅니다.

도착마을인 4를 제외하고 3 -> 4 경로에 있는 마을의 남은 용량의 최소는 40으로 20보다 큽니다.

그러면 to[3]에 20만큼 빼줍니다.

(ans = 70)

to[1] = 0, to[2] = 0, to[3] = 20

 

과정이 모두 끝났으니 ans를 출력해줍니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<int[]> list = new ArrayList<>();
    static int to[];
    static int N, C, M, ans;
 
    static void func() {
        for (int i = 0; i < M; i++) {
            int u = list.get(i)[0];
            int v = list.get(i)[1];
            int c = list.get(i)[2];
 
            int maxC = Integer.MAX_VALUE;
            for (int j = u; j < v; j++)
                maxC = Math.min(maxC, to[j]);
 
            if (maxC >= c) {
                for (int j = u; j < v; j++)
                    to[j] -= c;
                ans += c;
            } else {
                for (int j = u; j < v; j++)
                    to[j] -= maxC;
                ans += maxC;
            }
        }
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int u, v, c;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        to = new int[N + 1];
        Arrays.fill(to, C);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            list.add(new int[] { u, v, c });
        }
 
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1])
                    return a[0] - b[0];
                else
                    return a[1] - b[1];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16

www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

www.acmicpc.net

N개의 수업이 주어지면 강의실을 최소로 사용해서 모든 수업을 해야합니다.

저는 강의 시작시간 기준으로 정렬하였고, 우선순위 큐에 강의 종료시간을 넣었습니다.

 

q.peek()은 현재 진행중인 강의 중 가장 빠르게끝나는 강의이며, 다음 진행할 강의와 비교를 합니다 (x <= list[i][0])

x <= list[i][0]이면 같은 강의실에서 강의를 할 수 있으므로 remove를 해줍니다.

강의는 무조건 해야하므로 마지막에 끝나는 시간을 add 해줍니다.

마지막으로 q의 크기를 출력하시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N;
 
    static void func() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(list[0][1]);
        for (int i = 1; i < N; i++) {
            int x = q.peek();
 
            if (x <= list[i][0])
                q.remove();
            q.add(list[i][1]);
        }
 
        System.out.println(q.size());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0])
                    return a[1] - b[1];
                else
                    return a[0] - b[0];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29

www.acmicpc.net/problem/1931

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

회의실이 1개이고, 이를 사용할 수 있는 회의의 최대 갯수를 출력하는 문제입니다.

저는 회의 종료시간 기준으로 정렬한 후 그리디로 해결하였습니다.

 

회의 종료시간을 유지하면서 다음 회의부터 N까지 순회를 합니다.

현재 회의 종료시간이 다음 회의의 시작시간보다 작거나 같을때마다 종료시간을 갱신하고, ans를 1 늘려줍니다.

N번까지 순회 이후 ans를 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N, ans = 1;
 
    static void func() {
        int e = list[0][1];
        for (int i = 1; i < N; i++) {
            if (e <= list[i][0]) {
                e = list[i][1];
                ans++;
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1]) {
                    if (a[0] < b[0])
                        return -1;
                    else
                        return 1;
                } else {
                    if (a[1] < b[1])
                        return -1;
                    else
                        return 1;
                }
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29
boj 1339 단어 수학  (0) 2021.01.22

www.acmicpc.net/problem/2839

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

설탕 Nkg을 3kg 봉지와 5kg 봉지로 담는 그리디 문제입니다.

봉지가 담을 수 있는 무게가 3, 5 kg으로 한정되어있으니 설탕의 무게는 (3의배수 + 5의배수) kg이 됩니다.

 

우선 5kg이 가장 크기때문에 N이 5로 나누어떨어지면 모든 설탕을 5kg에 담으면 됩니다.

그렇지 않으면 3kg씩 빼주면서 다시 N이 5로 나누어떨어지는지 확인하는 방식으로 구현하였습니다.

 

만약 위의 과정에서 N이 5보다 작고 3의배수가 아니면 -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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
 
    static void func() {
        int ans = 0;
        while (true) {
            if (N % 5 == 0) {
                ans += (N / 5);
                N = 0;
            } else {
                ans++;
                N -= 3;
            }
 
            if (N == 0)
                break;
            
            if (N < 5 && N % 3 != 0) {
                ans = -1;
                break;
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29
boj 1339 단어 수학  (0) 2021.01.22

www.acmicpc.net/problem/11399

 

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

N명의 사람이 줄을 서는데 순서대로 돈을 인출하는데 걸리는 시간이 주어집니다.

 

[1, 2, 3]의 순서대로 줄을 서고 인출하는데 걸리는 시간이 [a, b, c]라고 하면

 

1이 먼저 인출하면 2, 3은 a만큼의 시간을 기다리게 됩니다.

그 다음 2가 인출하면 3은 b만큼의 시간을 더 기다려서 총 a+b만큼을 기다립니다.

 

줄을 어떻게 서냐에 따라 총 기다리는 시간이 달라지는데, 이를 최소화하여 모든 사람이 돈을 인출하는데 필요한 시간을 최소로 해야합니다.

 

기다리는 시간을 최소로 하기 위해서는 인출하는 시간이 적은 사람이 먼저 하면 됩니다.

저는 인출하는 시간을 오름차순으로 정렬하였고, dp로 간단하게 구현하였습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], dp[];
    static int N, ans;
 
    static void solve() {
        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i - 1] + list[i];
            ans += dp[i];
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        dp = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        solve();
    }
}
 cs

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

boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16
boj 1339 단어 수학  (0) 2021.01.22

www.acmicpc.net/problem/4889

 

4889번: 안정적인 문자열

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우

www.acmicpc.net

괄호가 주어지는대로 그리디하게 해결할 수 있는 문제입니다.

 

'{'가 주어지면 스택에 바로 push합니다.

'}'일때 스택이 비어있으면 ans에 1을 더하고 방향을 바꿔 '{'로 스택에 push합니다.

스택이 비어있지 않으면 pop을 해주면 됩니다.

 

이 과정을 반복한 후에 스택이 비어있지 않으면 '{'이 짝수개 남아있다는 말이 됩니다.

그래서 마지막에 s.size()/2를 더해주고 출력합니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Stack<Character> s = new Stack<>();
    static char ch[];
    static int ans = 0;
 
    static void func() {
        for (char x : ch) {
            if (x == '{') {
                s.push(x);
            } else {
                if (s.isEmpty()) {
                    ans++;
                    s.push('{');
                } else
                    s.pop();
            }
        }
 
        ans += (s.size() / 2);
        sb.append(ans + "\n");
        ans = 0;
        while (!s.isEmpty())
            s.pop();
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        for (int T = 1;; T++) {
            input();
            if (ch[0] == '-')
                break;
 
            sb.append(T + ". ");
            func();
        }
        
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 11279 최대 힙  (0) 2021.01.31
boj 1927 최소 힙  (0) 2021.01.31
boj 2504 괄호의 값  (0) 2021.01.26
boj 6198 옥상 정원 꾸미기  (0) 2021.01.26
boj 1874 수택 수열  (0) 2021.01.25

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

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

그리디로 해결 가능한 문제입니다.

 

알파벳이 ABC 이렇게 들어오면 앞에 있는 A부터 100의자리를 부여받고, 마지막에 있는 C는 1의자리를 받습니다.

이런 점을 이용하여 int배열을 알파벳 크기만큼 선언하여 뒤에서부터 C에 1을 더하고, B에 10을 더하고 A에 100을 더하는 방식으로 하였습니다.

 

이후에 더한 배열을 정렬하여 큰 수부터 9를 부여하는 식으로 값을 더해 출력하면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int num[] = new int[26];
    static int ans;
 
    static void func() {
        Arrays.sort(num);
        int n = 9;
        for (int i = 25; num[i] != 0; i--) {
            ans += (num[i] * n);
            n--;
        }
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
 
        while (N-- > 0) {
            int tmp = 1;
            st = new StringTokenizer(br.readLine());
            char ch[] = st.nextToken().toCharArray();
            for (int i = ch.length - 1; i >= 0; i--) {
                num[ch[i] - 'A'] += tmp;
                tmp *= 10;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16
boj 2839 설탕 배달  (0) 2021.02.16
boj 11399 ATM  (0) 2021.01.29

+ Recent posts

티스토리툴바