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 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16

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 16120 PPAP  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 1826 연료 채우기  (0) 2021.02.22
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (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/1826

 

1826번: 연료 채우기

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경

www.acmicpc.net

1km를 가는데 연료가 1L씩 소모됩니다.

목적지까지 가는 길에 주유소가 있어서 부족한 연료를 채우고 가야합니다.

마을에 도착했을 때, 주유소를 방문한 최소 횟수를 출력하는 문제입니다. 만약 목적지에 도착하지 못하면 -1을 출력합니다.

 

저는 거리 1당 1L이므로 연료소모를 하지않고 계속 쌓으면서 목적지까지 갈 수 있는지 확인하였고, 방법은 그리디로 하였습니다.

우선 입력으로 주어지는 주유소의 정보를 거리기준으로 오름차순 정렬합니다.

그 다음 현재 연료로 갈 수 있는 지점까지 큐에 넣어주면서 이동하다가

연료보다 더 멀리있는 주유소가 나오면 지금까지 큐에 넣어두었던 연료 중 가장 높은 값을 저장합니다.

물론 이를 위해 우선순위 큐를 사용합니다.

 

이 연산을 반복하여 마지막 목적지를 기준으로 연료가 충분한지도 확인해야합니다.

충분하면 그대로 ans를 출력, 모든 주유소를 다 들려도 목적지에 가지 못하면 -1을 출력합니다.

 

 

[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
54
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
priority_queue<int> q;
pair<int, int> list[10001];
int N, des, now, ans;
 
void func() {
    int idx = 0;
    while (idx < N) {
        if (now >= list[idx].first) {
            q.push(list[idx].second);
        }
        else {
            if (q.empty()) break;
            now += q.top();
            q.pop();
            ans++;
            idx--;
        }
        idx++;
    }
    while (!q.empty()) {
        if (now >= des) break;
        
        now += q.top();
        q.pop();
        ans++;
    }
 
    if (now >= des) cout << ans << '\n';
    else cout << "-1\n";
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    cin >> des >> now;
    sort(list, list + N);
}
 
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
62
63
64
65
66
67
68
69
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, des, now, ans;
 
    static void func() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int idx = 0;
        while (idx < N) {
            if (now >= list[idx][0])
                q.add(-list[idx][1]);
            else {
                if (q.isEmpty())
                    break;
 
                now -= q.poll();
                ans++;
                idx--;
            }
            idx++;
        }
 
        while (!q.isEmpty()) {
            if (now >= des)
                break;
            now -= q.poll();
            ans++;
        }
 
        if (now >= des)
            System.out.println(ans);
        else
            System.out.println(-1);
    }
 
    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());
        }
        st = new StringTokenizer(br.readLine());
        des = Integer.parseInt(st.nextToken());
        now = Integer.parseInt(st.nextToken());
 
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 2262 토너먼트 만들기  (0) 2021.10.16
boj 13904 과제  (0) 2021.09.30
boj 8980 택배  (0) 2021.02.16
boj 11000 강의실 배정  (0) 2021.02.16
boj 1931 회의실 배정  (0) 2021.02.16

 

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

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

티스토리툴바