글 읽기 - 왜 틀렸는지 모르겠어요. 반례 부탁드려요.

rdd6584 5년 전 1

end -> start로 정렬해서 그리디로 풀었는데요.

다른 사람들하고 코드를 비교해봐도, 같은 기능을 하는 로직이라고 생각이 들더군요.

이 문제에서 O(nm)으로 배열에 택배적재량을 그려서 하는 풀이와 제 풀이의 결과가 서로 다른 예제가 혹시 어떤게 있을까요?

#include <cstdio>
#include <queue>
#include <algorithm>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
const ll MOD = 1e9 + 7;

priority_queue<int, vector<int>, greater<int> > pq;
vector<int> v; deque<int> dq;

struct node {
	int s, e, cost;
} vec[10005];

queue<node> q;

int main() {
	int n, c, m, qt = 0, now = 0, sum = 0;
	scanf("%d %d %d", &n, &c, &m);

	for (int i = 0; i < m; i++)
		scanf("%d %d %d", &vec[i].s, &vec[i].e, &vec[i].cost);

	sort(vec, vec + m, [](node v1, node v2) {
		if (v1.e == v2.e) return v1.s < v2.s;
		return v1.e < v2.e;
	});


	// e - > s 순으로 정렬. 시뮬레이션으로 한칸씩 이동하면서
	// 트럭에 실은 택배는 queue에 넣어서 관리 해주는 방식.
	// now는 현재 트럭에 담겨있는 용량, qt는 택배상자 인덱스.
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && q.front().e <= i) {
			now -= q.front().cost;
			q.pop();
		}
		// 트럭에 실어있는 택배 중 배달이 완료된 것을 내림.

		while (now < c && qt < m) {
			if (vec[qt].s < i) { // 시기를 놓쳐 태울 수 없는 택배는 버림.
				qt++;
				continue;
			}
			int temp = min(vec[qt].cost, c - now);
			q.push({ vec[qt].s, vec[qt].e, temp });
			vec[qt].cost -= temp;
			now += temp;
			sum += temp;

			if (vec[qt].cost == 0) qt++;
		}
	}

	printf("%d", sum);
}

djm03178 5년 전 14

제 정답 코드와 비교해서 랜덤으로 돌려본 결과입니다.

4
5
4 1
5 3
5 1
4 2
2 2
correct = 9, wrong = 8

5
6
6 2
5 3
2 2
6 2
4 3
6 1
correct = 12, wrong = 10

5
4
4 1
3 4
2 1
4 4
correct = 7, wrong = 6

2
6
5 1
4 1
5 1
3 1
2 1
5 2
correct = 5, wrong = 4

5
4
3 2
5 3
4 1
4 1
correct = 6, wrong = 5

4
7
5 4
4 1
4 4
5 3
5 1
3 3
2 3
correct = 9, wrong = 8

4
10
6 2
6 1
5 2
4 2
6 1
6 1
3 2
2 4
5 2
6 2
correct = 13, wrong = 12

3
8
6 3
6 1
5 3
6 2
2 1
4 1
3 2
5 2
correct = 8, wrong = 7

4
12
6 4
4 3
6 4
5 4
5 4
5 4
6 3
4 4
5 1
6 3
3 3
2 3
correct = 18, wrong = 17

3
3
3 2
4 1
5 2
correct = 4, wrong = 3

rdd6584 5년 전 0

반례가 이렇게나 많군요.

진심으로 감사드립니다.

baepoce 4년 전 1

저는 예시와 다똑같이 나오는데 뭐가틀린걸까요

djm03178 4년 전 0

여기 있는 예시들은 이 코드가 틀린 부분을 저격하는 특징이 있는 거니까, 당연히 다른 틀린 코드의 약점까지 꼬집는다는 보장은 없습니다.

baepoce 4년 전 0

혹시 어떤게 문제인지 알려주실수 있나요? 고민해도 모르겠네요

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int c=sc.nextInt();
		int m=sc.nextInt();
		int arr[][]=new int[m][3];
		int t=1; //트럭위치
		int ans=0; //답
		int cnt=0; //택배박스량
		for(int i=0; i<m; i++)
		{
			arr[i][0]=sc.nextInt();
			arr[i][1]=sc.nextInt();
			arr[i][2]=sc.nextInt();	
			if(arr[i][0]==1)
			{			
				cnt+=arr[i][2];
				if(cnt>c)
					cnt=c;
			}
		}
		Arrays.sort(arr,new Comparator<int []>() {
			public int compare(int arr1[], int arr2[]) {
				if(arr1[1]==arr2[1])
					return Integer.compare(arr1[0],arr2[0]);
				return Integer.compare(arr1[1],arr2[1]);
			}
		});		
		while(t++<n)
		{
			for(int i=0; i<m; i++)
			{
				if(arr[i][1]==t) //박스마을에 내리기
				{
					if(cnt<arr[i][2])
					{
						ans+=cnt;
						cnt=0;
					}
					else
					{
						cnt-=arr[i][2];		
						ans+=arr[i][2];
					}
				}
				if(arr[i][0]==t) //박스트럭에 싣기
				{
					if(cnt+arr[i][2]>c)
					{
						cnt=c;
						continue;
					}
					else
					{		
						cnt+=arr[i][2];
					}				
				}
			}
		}
		System.out.print(ans);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀렸는지 모르겠어요. 반례 부탁드려요.

rdd6584 5년 전 1

djm03178 5년 전 14

rdd6584 5년 전 0

baepoce 4년 전 1

djm03178 4년 전 0

baepoce 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말