글 읽기 - 1931 문제 질문합니다.

xo294 4년 전 0

질문 글에 있는 반례 케이스 전부 맞는 것 같은데 왜 바로 틀렸습니다가 나오는지 잘 모르겠습니다.

테스트 케이스를 아래와 같이 정렬하였습니다.

0 6

1 4

2 13

3 5

3 8

5 7

5 9

6 10

8 11

8 12

12 14

이후 greedy 함을 이용하려고(?) 값의 차가 더 작다면 그 값을 적용하고,

뒤에 있는 값이 그 다음에 있는 값보다 작다면 그 값을 다시 적용하고 count를 더 올려주는 방향으로 적용하였습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int prev, now, cases, cnt = 1;
	vector<pair<int, int>> v;
	pair<int, int> tmp;
	cin >> cases;
	for (int i = 0; i < cases; i++) 
		cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());
	tmp.first = v[0].first; tmp.second = v[0].second;

	for (int i = 1; i < cases; i++) {
		//cout << v[i].first << ' ' <<  v[i].second << '\n';
		prev = tmp.second - tmp.first;
		now = v[i].second - v[i].first;
		if (tmp.second <= v[i].first) {
			tmp.first = v[i].first; tmp.second = v[i].second;
			cnt++;
		}
		else if (prev > now) {
			tmp.first = v[i].first; tmp.second = v[i].second;
		}
	}
	cout << cnt;
}

lucian0910 4년 전 1

정렬 및 알고리즘 사용이 틀렸습니다. 간단하게 틀린 예 알려드립니다.

0 4

2 5

4 6

이 때 1번, 3번 것이 사용되서 2가 답이지만 위대로 하면 2번째 것만 사용되서 1이 출력됩니다.

lucian0910 4년 전 1

추가로 vector 사용할 시 처음에는 공간이 없기 때문에 12번째 줄의 cin >> v[i].first >> v[i].second 는 잘못된 사용법입니다. vector 사용할 시 push_back() 멤버함수를 이용해야 됩니다.

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

문제

문제

출처

ICPC

1931 문제 질문합니다.

xo294 4년 전 0

lucian0910 4년 전 1

lucian0910 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말