글 읽기 - 어떤 반례가 있을까요??

94kaiser 3년 전 0

채점해보면, 50% 에서 실패가 발생되고 있습니다.

도저히 반례를 못 찾겠는데요, 어떤 반례가 있을까요???

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static HashMap<String, String[]> map = new HashMap();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringBuilder builder = new StringBuilder();

        int M = sc.nextInt();
        int[] inputs = new int[M];

        for (int i = 0 ; i < M ; i++) {
            inputs[i] = sc.nextInt();
        }
        Arrays.sort(inputs);

        for (int i = M - 1 ; i >= 0 ; i--) {
            int v = inputs[i];
            int x = 0, y = 0, z = 0;

            for (int a = i - 1 ; a >= 0 ; a--) {
                x = inputs[a];
                for (int b = a - 1 ; b >= 0 ; b--) {
                    y = inputs[b];

                    if ( x + y > v) {
                        continue;
                    }
                    for (int c = b - 1 ; c >= 0 ; c--) {
                        z = inputs[c];

                        if ( x + y + z > v) {
                            continue;
                        }

                        if ( x + y + z == v) {
                            System.out.println(v);
                            return;
                        }
                    }
                }
            }
        }
    }
}

plan222 3년 전 1

x, y, z, k가 서로 같아도 된다.

중복 선택이 됩니다.

94kaiser 3년 전 0

x, y, z, k가 서로 같아도 된다 는 것이 어떤 의미일까요??

어떤 Case의 데이타가 있을 수 있을까요??

아래와 같은, 데이타가 주어졌을때, 10 + 10 + 10 = 30 이 될수 있다는 의미 일까요??

plan222 3년 전 0

네 그런식으로도 가능하다는 뜻이예요.

직접 코드 몇줄만 수정하니까 맞더라고요.

94kaiser 3년 전 0

얘기해주신대로, 중복 선택 Case를 고려해서, for loop 를 약간 변경하니 pass되네요. 감사합니다.

pmn0001 2년 전 0

안녕하세요 문제 풀다가 O(n^3)은 통과가 안될 것 같아서 다른방식으로 시도하다가 실패해서 이 글에 있는 코드 수정해서 통과됐는데요

혹시 O(n^3) 풀이가 원래 통과가 되는 문제인가요? 아니면 이 코드는 O(n^3) 이 아닌 건지.. 감사합니다

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

문제

문제

출처

ICPC

어떤 반례가 있을까요??

94kaiser 3년 전 0

plan222 3년 전 1

94kaiser 3년 전 0

plan222 3년 전 0

94kaiser 3년 전 0

pmn0001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말