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

itlockit 5년 전 0

제가 생각한 알고리즘은

flag를 이용해서 한번은 작은수를 맨앞에 큰수를 맨뒤에

한번은 큰수를 맨앞에 작은수를 맨뒤에 집어넣고

만약 N이 홀수일때는 맨앞과 맨뒤중 차이가 큰곳에 넣는것인데

게시글에 존재하는 반례 다 넣었을때는 정상작동 하는거 확인했습니다.

혹시 다른 반례가 있을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class bj10819 {
    public static void main(String[] args) throws IOException {
        ArrayList<Integer> numbers = new ArrayList<>();
        ArrayList<Integer> results = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
           numbers.add(Integer.parseInt(st.nextToken()));
        }
        // Sort
        Collections.sort(numbers);
        int small = 0;
        int big = numbers.size()-1;
        // flag
        boolean turn = true;
        while(small <= big){
            if(turn) {
                turn = false;
                results.add(0, numbers.get(small));
                results.add(numbers.get(big));
            } else if(small == big){
                int first = Math.abs(results.get(0) -  numbers.get(small));
                int end = Math.abs(results.get(results.size() -1 ) - numbers.get(small));
                if(first < end){
                    results.add(numbers.get(small));
                } else {
                    results.add(0,numbers.get(small));
                }
            } else {
                turn = true;
                results.add(numbers.get(small));
                results.add(0,numbers.get(big));
            }
            small++;
            big--;
        }
        int result = 0;
        for(int i = 0 ; i < results.size() - 1 ; i++){
            result = result + Math.abs(results.get(i) - results.get(i+1));
        }
        System.out.println(result);
    }
}

arhbit 5년 전 0

정답은 374
위 소스코드로는 394가 나옵니다.

5
-66 -86 51 -87 -27

itlockit 5년 전 0

감사합니다. if문 순서가 문제였네요.

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

문제

문제

출처

ICPC

반례가 있을까요??

itlockit 5년 전 0

arhbit 5년 전 0

itlockit 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말