글 읽기 - 반례좀 들어주세요!!

dudgns3781 1년 전 0

이정도면 된거 같은데 도대체 반례를 모르겠어요

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N,check,n;
    int arr[100000] = {};
    int* p = arr;

    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> arr[i];

    if (N == 1) { cout << arr[0]; return 0; }

    sort(p, p + N);
    n = N;
    for (int i = 0; i < N; i++)
        if (arr[i] * n < arr[N - 1]) {
            arr[i] = 0;
            n -= 1;
        }

    for (int i = 0;i < N ;i++)
        if (arr[i] != 0) {
            check = i;
            break;
        }
    if (n > 1) cout << long(arr[check] * n);
    else if(n == 1) cout << arr[check];

    return 0;
}

hhs5125 1년 전 0

위의 코드에서의 문제점을 설명하자면

arr[a] * (N-a) >= arr[N-1]을 만족하는 a의 개수는 많을 수 있고,

위를 만족하는 두 숫자(a) i,j (i<j)에 대해 arr[i]*(N-i) < arr[j]*(N-j)인 경우는 있을 수 있습니다.

위 경우를 체크하지 않고 처음 arr[i] != 0인 것을 만나면 바로 break를 해버리기 때문에 코드에 오류가 있는 것 같습니다.

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

문제

문제

출처

ICPC

반례좀 들어주세요!!

dudgns3781 1년 전 0

hhs5125 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말