글 읽기 - 반례 부탁드리겠습니다.

dyddkdlel33 5년 전 0

DP로 풀지 않았는데 이 코드의 문제점이 무엇인지 알 수 있을까요? 참고로 테스트 케이스에서는 다 맞았습니다.

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

struct point {
	int price;  // 실제 값
	double unit;   // 단위 값
	int index;  // index 값. index는 물량으로도 표현 됨.
};

bool comp(const point &p1, const point &p2){
	if (p1.unit < p2.unit)
		return true;
	else 
		return false;
	

}

int main() {
	point dp[10000];
	int N;
	int result=0; //결과값
	int share, remain;

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {  // 1부터 N까지로 배열에 설정.
		scanf("%d", &dp[i].price);   // 실제값 먼저 저장.
	}
	for (int i = 0; i < N; i++) {
		dp[i].unit = (double) dp[i].price / (i+1);  // 단위 가격 저장.
		dp[i].index = i+1;  // index 값 저장.
	}
	sort(dp, dp + N, comp);
	// unit으로 sort를 진행했고, price와 index로 알고리즘을 만들 것이다.
	
	share = N;
	for (int i = N-1; i >=0; i--) { // 0부터 sort가 진행될 것임.
		if (share >= dp[i].index) {
			remain = share % dp[i].index; // 나머지를 먼저 출력. 후에 0인지를 확인하기 위함.
			share = share / dp[i].index;
			result += dp[i].price * share;
			if (remain == 0)
				break;
		}
		else
			continue;
	}
	printf("%d", result);
	return 0;
}

luniro 5년 전 0

문제 번호를 표시해주세요

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

문제

문제

출처

ICPC

반례 부탁드리겠습니다.

dyddkdlel33 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말