글 읽기 - 반례점 찾아주세요

tnswh213 3년 전 0

반례를 찾아주시면 감사하겠습니다. ㅜㅜ

#include

#include

using namespace std;

int N = 0;

int minValue = 99999;

int* lopes = nullptr;

int result = 0;

int myindex = 0;

int sol(int num);

int main()

{

cin >> N;

lopes = new int[N];

memset(lopes, 0, sizeof(N));

for (int i = 0; i < N; i++) {

cin >> lopes[i];

}

cout << sol(N);

if (lopes)

delete[] lopes;

}

int sol(int num)

{

minValue = 99999;

for (int i = 0; i < N; i++)

{

if (lopes[i] < minValue && lopes[i] != 0) {

minValue = lopes[i];

myindex = i;

}

}

lopes[myindex] = 0;

if (result > minValue * num)

return result;

result = minValue * num;

sol(num - 1);

if (num == 1)

return result;

}

amoretspero 3년 전 1

로프 중량이 중복될 수도 있는데 myindex 변수를 사용해서 lopes[myindex]=0으로 설정하는 것이 현재 각 로프들이 들 수 있는 무게들 중 최소인 로프들 중에서 첫 번째 로프만 0으로 설정하는거라서 최소 중량이 중복되는 경우에 문제가 발생할 수 있을 것 같아요.

정도면 최소 반례가 될 듯 합니다. 4짜리 로프 1개로 들어올리는 무게 4가 최대이나, 올리신 코드로 실행하면 3 나올 것 같네요.

tnswh213 3년 전 0

답변 감사합니다.

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

문제

문제

출처

ICPC

반례점 찾아주세요

tnswh213 3년 전 0

amoretspero 3년 전 1

tnswh213 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말