글 읽기 - 반례나 제 코드의 문제점을 알 수 있을까요?

tjdgnsqn3 5년 전 0

양 끝에서

서로 만나는 느낌으로 작동됩니다.

반례를 못찾겠네요...

예제 입력이랑 제가 만들어본 테스트 케이스

-100 -1 0 1 50 51

는 잘 작동됩니다.

#include <cstdio>
/**
 * https://www.acmicpc.net/problem/14921
 * BOJ 백준온라인져지 14921 용액 합성하기 풀이
 */
using namespace std;
int abs(int a){
    return a > 0 ? a : -a;
}
int min(int a, int b){
    int aa = abs(a);
    int bb = abs(b);
    return aa < bb ? a : b;
}
int main(){
    int N;
    scanf("%d", &N);
    int *list = new int[N];
    for(int i = 0; i < N; i++){
        scanf("%d", &list[i]);
    }
    int maximum = 1000000000, l = 0, r = N - 1;
    do{
        if(abs(maximum) > abs(list[l] + list[r])){
            maximum = list[l] + list[r];
        }
        if(abs(list[l] + list[r]) > abs(list[l] + list[r - 1])){
            r--;
        }else if(r + 1 < N && abs(list[l] + list[r]) > abs(list[l] + list[r + 1])){
            r++;
        }else{
            l++;
        }
    }while(l < r);
    printf("%d", maximum);
}

tjdgnsqn3 5년 전 0

2%에서 틀립니다.

tjdgnsqn3 5년 전 0

1 -1 2 2

용액의 값이 중복이 되는군요.

worn1215 5년 전 0

죄송 하지만

1 -1 2 2

는 반례가 될 수 없습니다.

입력이 항상 오름차순으로 들어가기 때문입니다.

tjdgnsqn3 5년 전 0

1 -1 2 2

중복되는 특성값이 있다는 조건을 체크해주니까 정답이 됐습니다...

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

문제

문제

출처

ICPC

반례나 제 코드의 문제점을 알 수 있을까요?

tjdgnsqn3 5년 전 0

tjdgnsqn3 5년 전 0

tjdgnsqn3 5년 전 0

worn1215 5년 전 0

tjdgnsqn3 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말