글 읽기 - 반례를 알 수 있을까요?

soojinyi98 3년 전 0

a b c d e f 를 비교한다고 했을 때

a-f 가 초기값,

a-e, b-f, 둘 다 아니면 b-e 순서대로 최솟값이 바뀌고,

셋 다 아니면

a-f 를 출력하는 식으로 만들어보았는데 틀렸다고 나오네요.

반례를 못 찾겠습니다ㅠㅠ

#include <stdio.h>

/**
 * https://www.acmicpc.net/problem/14921
 * BOJ 백준온라인져지 14921 용액 합성하기 풀이
 */

int abs(int a) {
	return a > 0 ? a : -a;
}


int main(void) {
	int num;
	int arr[100000] = { 0, };

	// 숫자를 하나씩 numArr에 저장
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d", &arr[i]);
	}

	int left = 0; int right = num - 1;
	int min = abs(arr[left] + arr[right]);
	while (left < right) {
		int sign = 0;
		if ((min >= abs(arr[left] + arr[right - 1])) && (left != right - 1)) {
			min = abs(arr[left] + arr[right - 1]);
			right--;
			sign = 1;

		}
		if ((min >= abs(arr[left + 1] + arr[right])) && (left + 1 != right)) {
			min = abs(arr[left + 1] + arr[right]);
			left++;
			sign = 1;
		}
		if ((sign==0)&&(min >= abs(arr[left + 1] + arr[right - 1])) && (left + 1 != right-1)){
			min = abs(arr[left + 1] + arr[right - 1]);
			left++;
			right--;
			sign = -1;
		}
		int min = abs(arr[left] + arr[right]);
		if (sign == 0)
			break;
	}
	printf("%d", min);
	return 0;
}

mickeyjung 3년 전 1

-7 -4 -1 1 2 6

일때 1이 출력 되네요

이게 반례인것 같습니다.

----------------------------------

제가 한번 다시 짜봤는데요

초기값으로 s를 0 e를 n-1로 설정하고

만약에 a[s]+a[e]가 0보다 크면 e를 감소시키고

아니면 s를 증가시킵니다.

ans에는 a[s]+a[e]의 최솟값을 저장하면 되겠죠?

그러다가 s와 e가 같아지면 while문을 종료하게 됩니다.

#include <bits/stdc++.h>

using namespace std;

int n;
int a[100001],ans;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int s=0,e=n-1;
    ans=a[s]+a[e];
    while(1){
        if(a[s]+a[e]>0)e--;
        else s++;
        if(s>=e)break;
        if(abs(a[s]+a[e])<abs(ans)){
            ans=a[s]+a[e];
        }
    }
    printf("%d",ans);

    return 0;
}

soojinyi98 3년 전 0

감사합니다! 큰 도움이 되었습니다.

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

문제

문제

출처

ICPC

반례를 알 수 있을까요?

soojinyi98 3년 전 0

mickeyjung 3년 전 1

soojinyi98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말