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 |