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

 

10800번: 컬러볼

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N

www.acmicpc.net

 

어떤 공은 자신보다 색이 같거나 크기가 크거나 같은 공을 잡을 수 없습니다.

즉, 색이 다르고, 크기가 작은 공을 잡을 수 있습니다.

 

저는 공의 색에 대한 누적합(colorsum), 크기에 대한 누적합(sizesum), 전체 누적합(sum)을 모두 구하면서 답을 찾았습니다.

 

우선 공의 크기 -> 색 별로 오름차순 정렬합니다. (출력할 때 인덱스를 맞춰줘야하니 인덱스를 유지해줍니다.)

이제 크기가 작은 공부터 하나씩 꺼내 sum, colorsum, sizesum을 갱신합니다.

 

그럼 현재 공이 잡을 수 있는 공은

전체 합 - 같은 색의 크기 합 - 같은 크기의 크기 합 + 자신의 크기로 구해주시면 됩니다.

(같은 색과 같은 크기는 잡을 수 없으며 자신은 두 번 뺀 값이기때문에 자신의 크기를 더한 것입니다.)

 

하지만 이걸로 끝내기엔 예외가 하나 더 있습니다.

"자신과 색과 크기 모두 같은 공" 끼리는 답이 모두 같습니다.

저는 여기에서 예외처리가 안되어 pre배열에 이전 공의 정보를 유지하였습니다.

이전 공의 색과 크기가 모두 같으면 이전 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
74
75
76
77
78
79
80
81
82
83
84
85
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static class Pair {
        int idx;
        int color;
        int size;
 
        public Pair(int idx, int color, int size) {
            this.idx = idx;
            this.color = color;
            this.size = size;
        }
    }
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Pair> list;
    static int sum[] = new int[200001];
    static int colorsum[] = new int[200001];
    static int sizesum[] = new int[2001];
    static int ans[] = new int[200001];
    static int N;
 
    static void func() {
        int pre[] = new int[3];
        for (int i = 1; i <= N; i++) {
            int idx = list.get(i - 1).idx;
            int color = list.get(i - 1).color;
            int size = list.get(i - 1).size;
 
            sum[i] = sum[i - 1] + size;
            colorsum[color] += size;
            sizesum[size] += size;
 
            if (color == pre[1] && size == pre[2])
                ans[idx] = ans[pre[0]];
            else
                ans[idx] = sum[i] - colorsum[color] - sizesum[size] + size;
 
            pre[0] = idx;
            pre[1] = color;
            pre[2] = size;
        }
 
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append("\n");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        int x, y;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            list.add(new Pair(i, x, y));
        }
 
        Collections.sort(list, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if (o1.size == o2.size)
                    return o1.color - o2.color;
                else
                    return o1.size - o2.size;
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 13325 이진 트리  (0) 2021.06.18
boj 1563 개근상  (0) 2021.06.02
boj 12869 뮤탈리스크  (0) 2021.04.04
boj 1520 내리막 길  (0) 2021.03.28
boj 1937 욕심쟁이 판다  (0) 2021.03.28

 

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

+ Recent posts

티스토리툴바