[백준] 택배

[hye-on]

🔗 택배

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 14:32 시작! */ public class Main { /* * 그리디 * 1 2 10 : 1번에서 +10 * 1 3 20 : 1-2번에서 +20 * 2 3 10 : 2번에서 +10 * 1 4 30 : 1-3번에서 +10 * 2 4 20 * 3 4 20 : 3번에서 +20 */ public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); int n = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(bf.readLine()); int[][] info = new int[m][3]; for(int i = 0; i < m; ++i) { st = new StringTokenizer(bf.readLine()); info[i][0] = Integer.parseInt(st.nextToken()); info[i][1] = Integer.parseInt(st.nextToken()); info[i][2] = Integer.parseInt(st.nextToken()); } Arrays.sort(info, (a, b) -> a[1] - b[1] == 0 ? a[0] - b[0] : a[1] - b[1]); int[] remain = new int[n+1]; Arrays.fill(remain, c); int count = 0; for(int i = 0; i < m; ++i) { int from = info[i][0]; int to = info[i][1]; int cnt = info[i][2]; for(int j = from; j < to; ++j) { cnt = Math.min(cnt, remain[j]); } if(cnt == 0) continue; for(int j = from; j < to; ++j) { remain[j] -= cnt; } count += cnt; } System.out.println(count); } } ```

코멘트

- 처음에는 보내는 마을 기준으로 정렬을 생각해서 그리디 문제가 아닌 줄 알았네요😢 알고보니 도착하는 마을을 기준으로 정렬하고(최대한 빨리 내려줘야 뒤에 더 내려줄 수 있기 때문) 그리디로 풀면 되는 문제였습니다!

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, c, m; cin >> n >> c >> m; vector> v(m); // {도착, 시작, 박스} for (int i = 0; i < m; i++) { int start, end, box; cin >> start >> end >> box; v[i] = { end, start, box }; // 도착지 기준 정렬을 위해 end를 첫번째로 } sort(v.begin(), v.end()); // 기본 정렬만으로 도착지, 시작지 순 정렬됨 vector capacity(n + 1, c); int ans = 0; for (int i = 0; i < m; i++) { int end = get<0>(v[i]); int start = get<1>(v[i]); int box = get<2>(v[i]); int possible = c; for (int j = start; j < end; j++) { possible = min(possible, capacity[j]); } int mBox = min(possible, box); for (int j = start; j < end; j++) { capacity[j] -= mBox; } ans += mBox; } cout << ans << '\n'; return 0; } ```

코멘트

- 출발하는 도시를 기준으로 정렬하고 도착하는 애가 더 빠른 것이 등장할 경우 교체하는 것으로 풀었는데 틀린 엣지 케이스가 계속 있었던 것 같습니다 ㅠ 도착하는 도시 기준으로 정렿해서 풀어야했네요