글 읽기 - 그리디라고 생각했는데 반례가 있을까용? ㅠㅠ

gktgnjftm 5년 전 0

결국에 저 프로젝트가 한번에 되려면

1~n까지의 수로 이루어져 있어야 된다고 생각을 했습니다.

그래서 입력받은 숫자와 일치하는것이 있으면 걔네들은 따로 빼고,

일치하지 않는 숫자들끼리 차이를 누적해서 더하는 식으로 생각을 했습니다

생각이 틀릴수도 있을거같은데 우선은 반례나 다른 해법이 떠오르질 않습니다 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;
#define INF 1000000000
typedef pair<int, int> P;
typedef pair<ll, pair<ll, ll>> PP;
typedef pair<pair<int, int>, pair<int, int>> PPP;
int gox[4] = { 0,0,1,-1 };
int goy[4] = { 1,-1,0,0 };
int n;
map<int, int> check;
bool numvisited[100005];
bool visited[100005];
int main() {
	scanf("%d", &n);
	vector<int> v;
	vector<int> origin;
	for (int i = 1; i <= n; i++) origin.push_back(i);
	for (int i = 1; i <= n; i++) {
		int num;
		scanf("%d", &num);
		v.push_back(num);
	}
	sort(v.begin(),v.end());
	vector<int>::iterator it;
	for (int i = 1; i <= n; i++) {
		it = lower_bound(v.begin(), v.end(), i);
		if (*it == i) {
			numvisited[i] = true; // 1~n까지의 숫자들을 체크
		}
	}
	for (int i = 0; i < v.size(); i++) {
		it = lower_bound(origin.begin(), origin.end(), v[i]);
		if (it == origin.end()) continue;
		if (*it == v[i]) {
			if (check.count(v[i]) == 0) {
				check[v[i]] = 1; // 입력받은 배열에서 같은 숫자가 있는지 체크
				visited[i] = true;
			}
		}
	}
	vector<int> real,real2;
	for (int i = 0; i < v.size(); i++) {
		if (!visited[i]) {
			real.push_back(v[i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!numvisited[i]) {
			real2.push_back(i);
		}
	}
	ll sum = 0;
	for (int i = 0; i < real.size(); i++) {
		sum += abs(real[i] - real2[i]); // 그차이를 누적시킴
	}
	printf("%lld\n", sum);
	return 0;
}

dyk777 5년 전 1

https://ideone.com/23ldFd

답은 2입니다.

gktgnjftm 5년 전 0

좋은 반례 감사합니당 ^^

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

문제

문제

출처

ICPC

그리디라고 생각했는데 반례가 있을까용? ㅠㅠ

gktgnjftm 5년 전 0

dyk777 5년 전 1

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말