글 읽기 - 오답반례 질문입니다. 이건 맞는거아닌가요?

temp 7년 전 0

먼저 저는 이 문제의 정답을 맞지 못하였습니다. 구글링을 통해 정답자의 소스로 정답이 나온것이며, 저는 이 정답이 틀렸다고 생각하였습니다.

먼저 제가 생각한 인풋은 다음과 같습니다.

50 17 15 16 9

위 5가지 숫자가 들어왔을때 만약 / - - 와 괄호를 사용한다면

50 / (17-15) -16 = 9

이렇게 나올텐데요...그럼 OK가 나와야 하는것 아닌가요? 왜 이게 정답소스에서는 NO라고 하는걸까요?

제가 문제를 잘못 이해하고 있는것인지 모르겠습니다. 아무리 고쳐도 정답이 나오지 않아 글을 적습니다.

temp 7년 전 0

같은 규칙으로
30 4 2 5 10

이수를 사용하면 정답소스에서는 ok를 주고있습니다.

물론 제 소스도 ok를 줍니다. 하지만 같은 규칙인데 본문의 수들은 no를 주고 여기서는 ok를 준다는게
이건 뭔가 이상하다고 생각합니다.

simm4256 7년 전 0

문제를 푸는 중인데 참...

문제에 반드시 필요한 설명들이 빠진 게 많아보이네요

n1~n4의 순서를 바꿔도 되느냐에 대한 설명도 없고

괄호를 연산자로 취급하는것처럼 말하더니 정답소스에선 괄호는 따로취급하고..

푸는중이라 뭐라고 말씀드릴 순 없는데

두 번째 예를 드신

30 4 2 5 10

의 경우

30 / 4 * 2 - 5 = 10

으로 괄호없이 OK처리가 되는 예제이긴 합니다.

근데 정답소스코드에서

5 2 3 5 125를 OK처리하는걸로 봐선

5 * (2 + 3) * 5 = 125

라고 본 것 같은데

질문자님의 첫번 째 예제와 같은 위치의 괄호인데.. 어째서 NO라고 출력되는지는 잘 모르겠네요

temp 7년 전 0

문제가 많이 애매모호하다고 생각합니다.

특정 경우에 대해서는 허락하고 안하고 이러는것같다는 생각입니다..

simm4256 7년 전 0

일단 정답소스에선

a # ( b # c) # d

에 대한 처리를 안해줬네요.

근데 저 경우로만 풀어야 하는 연산은

예로 드신

a / (b - c) - d

밖에 없습니다.

이 외의 다른 연산자가 들어갈 경우 a~d의 순서를 바꿔 다른 모양의 괄호가 나오도록 할 수가 있네요.

제가 볼땐 테스트케이스에 저런 식이 없는 것 같습니다.

한번 본인 소스에서 저 경우만 제외하고 제출했을 때 어떻게 뜨는지 해봐주시면 안될까요?

temp 7년 전 0

저 경우를 제외하니 틀렸다고 나오네요.

simm4256 7년 전 0

혹시 소스 볼 수 있을까요?

temp 7년 전 0

소스는 다음과 같습니다.

#include<iostream>
#include<algorithm>
using namespace std;
double arr[5], ans;
char sym[3];
//case 1 (a, b), c, d
//case 2 a, (b, c), d
//case 3 a, b, (c, d)
//case 4 (a, b), (c, d)
//case 5 (a, b, c), d
//case 6 a, (b, c, d)
//case 7 a, b, c, d
void make_sym(int idx);
void chk(double temp[]);
double _cal2(double a, double b, char symbol);
double _cal3(double a, double b, double c, char symbol1, char symbol2);
double _cal4();
 
int main()
{
 
    while (cin >> arr[0] && arr[0] != -1)
    {
        for (int i = 1; i < 5; i++)  cin >> arr[i];
        for (int i = 0; i < 5; i++) cout << arr[i] << ' ';
 
        sort(arr, arr + 4);
        do {
            make_sym(0);
            if (ans == 1) break;
        } while (next_permutation(arr, arr + 4));
     
        if (ans) cout << "OK!" << endl;
        else cout << "NO!" << endl;
         
        ans = 0;
    }
    return 0;
}
void make_sym( int idx)
{
    if (ans == 1) return;
 
    if (idx == 3)
    {
        double temp[7] = {0, };
 
        temp[0] = _cal3(_cal2(arr[0], arr[1], sym[0]), arr[2], arr[3], sym[1], sym[2]);
        //temp[1] = _cal3(arr[0], _cal2(arr[1], arr[2], sym[1]), arr[3], sym[0], sym[2]);
        temp[2] = _cal3(arr[0], arr[1], _cal2(arr[2], arr[3], sym[2]), sym[0], sym[1]);
        temp[3] = _cal2(_cal2(arr[0], arr[1], sym[0]), _cal2(arr[2], arr[3], sym[2]), sym[1]);
        temp[4] = _cal2(_cal3(arr[0], arr[1], arr[2], sym[0], sym[1]), arr[3], sym[2]);
        temp[5] = _cal2(arr[0], _cal3(arr[1], arr[2], arr[3], sym[1], sym[2]), sym[0]);
        temp[6] = _cal4();
 
        //cout << sym[0] << ' ' << sym[1] << ' ' << sym[2] << endl;
        chk(temp);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (i == 0) sym[idx] = '+';
        else if (i == 1) sym[idx] = '*';
        else if (i == 2) sym[idx] = '-';
        else sym[idx] = '/';
 
        make_sym(idx + 1);
    }
}
void chk(double temp[])
{
    for (int i = 0; i < 7; i++)
    {
        //cout << temp[i] << ' ';
        if (temp[i] == arr[4])
        {
            ans = 1;
            return;
        }
    }
    //cout << endl;
}
double _cal2(double a, double b, char symbol)
{
    double temp = 0;
    if (symbol == '+') temp = a + b;
    else if (symbol == '-') temp = a - b;
    else if (symbol == '*') temp = a * b;
    else if(symbol=='/' && b!=0) temp = a / b;
     
    return temp;
}
double _cal3(double a, double b, double c, char symbol1, char symbol2)
{
    double temp;
    if ((symbol2 == '*' || symbol2 == '/') && (symbol1 == '+' || symbol1 == '-'))
    {
        temp = _cal2(b, c, symbol2);
        temp = _cal2(a, temp, symbol1);
    }
    else
    {
        temp = _cal2(a, b, symbol1);
        temp = _cal2(temp, c, symbol2);
    }
    return temp;
}
double _cal4()
{
    double temp = 0;
 
    if (sym[1] == '*' || sym[1] == '/')
        temp = _cal3(arr[0], _cal2(arr[1], arr[2], sym[1]), arr[3], sym[0], sym[2]);
    else if (sym[2] == '*' || sym[2] == '/')
        temp = _cal3(arr[0], arr[1], _cal2(arr[2], arr[3], sym[2]), sym[0], sym[1]);
    else
        temp = _cal3(_cal2(arr[0], arr[1], sym[0]), arr[2], arr[3], sym[1], sym[2]);
     
    return temp;
}

simm4256 7년 전 1

질문자님 소스 맞았습니다.

그 경우 제외하실 때 주석처리만 하시면

temp[1] = 0으로 기본값이 남기 때문에

답이 0이 될 수 없는 테스트 케이스인데 temp[1]=0이라 chk(temp)에서 ans=1이되는 경우가 발생하더군요

그래서 아예 temp 배열 크기를 6으로하고 해봤더니 정답이라고 뜨네요

결론은, 현재 테스트케이스에선 a / (b - c) - d = e 로만 답이 나오는 입력이 없다는거네요.

#include<iostream>
#include<algorithm>
using namespace std;
double arr[5], ans;
char sym[3];
//case 1 (a, b), c, d
//case 2 a, (b, c), d
//case 3 a, b, (c, d)
//case 4 (a, b), (c, d)
//case 5 (a, b, c), d
//case 6 a, (b, c, d)
//case 7 a, b, c, d
void make_sym(int idx);
int chk(double temp[]);
double _cal2(double a, double b, char symbol);
double _cal3(double a, double b, double c, char symbol1, char symbol2);
double _cal4();

int main()
{

	while (cin >> arr[0] && arr[0] != -1)
	{
		for (int i = 1; i < 5; i++)  cin >> arr[i];
		for (int i = 0; i < 5; i++) cout << arr[i] << ' ';

		sort(arr, arr + 4);
		do {
			make_sym(0);
			if (ans == 1) break;
		} while (next_permutation(arr, arr + 4));

		if (ans) cout << "OK!" << endl;
		else cout << "NO!" << endl;

		ans = 0;
	}
	return 0;
}
void make_sym(int idx)
{
	if (ans == 1) return;

	if (idx == 3)
	{
		double temp[6] = { 0, };

		temp[0] = _cal3(_cal2(arr[0], arr[1], sym[0]), arr[2], arr[3], sym[1], sym[2]);
		//temp[1] = _cal3(arr[0], _cal2(arr[1], arr[2], sym[1]), arr[3], sym[0], sym[2]);
		temp[1] = _cal3(arr[0], arr[1], _cal2(arr[2], arr[3], sym[2]), sym[0], sym[1]);
		temp[2] = _cal2(_cal2(arr[0], arr[1], sym[0]), _cal2(arr[2], arr[3], sym[2]), sym[1]);
		temp[3] = _cal2(_cal3(arr[0], arr[1], arr[2], sym[0], sym[1]), arr[3], sym[2]);
		temp[4] = _cal2(arr[0], _cal3(arr[1], arr[2], arr[3], sym[1], sym[2]), sym[0]);
		temp[5] = _cal4();

		//cout << sym[0] << ' ' << sym[1] << ' ' << sym[2] << endl;
		//int temppp =  chk(temp);
		chk(temp);
		//if (temppp != -23) 
			//cout << arr[0] << sym[0] << arr[1] << sym[1] << arr[2] << sym[2] << arr[3] << " = " << arr[4] << " // " << temppp << endl;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		if (i == 0) sym[idx] = '+';
		else if (i == 1) sym[idx] = '*';
		else if (i == 2) sym[idx] = '-';
		else sym[idx] = '/';

		make_sym(idx + 1);
	}
}
int chk(double temp[])
{
	for (int i = 0; i < 6; i++)
	{
		//cout << temp[i] << ' ';
		if (temp[i] == arr[4])
		{
			ans = 1;
			return i;
		}
	}
	//cout << endl;
	return -23;
}
double _cal2(double a, double b, char symbol)
{
	double temp = 0;
	if (symbol == '+') temp = a + b;
	else if (symbol == '-') temp = a - b;
	else if (symbol == '*') temp = a * b;
	else if (symbol == '/' && b != 0) temp = a / b;

	return temp;
}
double _cal3(double a, double b, double c, char symbol1, char symbol2)
{
	double temp;
	if ((symbol2 == '*' || symbol2 == '/') && (symbol1 == '+' || symbol1 == '-'))
	{
		temp = _cal2(b, c, symbol2);
		temp = _cal2(a, temp, symbol1);
	}
	else
	{
		temp = _cal2(a, b, symbol1);
		temp = _cal2(temp, c, symbol2);
	}
	return temp;
}
double _cal4()
{
	double temp = 0;

	if (sym[1] == '*' || sym[1] == '/')
		temp = _cal3(arr[0], _cal2(arr[1], arr[2], sym[1]), arr[3], sym[0], sym[2]);
	else if (sym[2] == '*' || sym[2] == '/')
		temp = _cal3(arr[0], arr[1], _cal2(arr[2], arr[3], sym[2]), sym[0], sym[1]);
	else
		temp = _cal3(_cal2(arr[0], arr[1], sym[0]), arr[2], arr[3], sym[1], sym[2]);

	return temp;
}

simm4256 7년 전 0

아, 테스트케이스 추가해달라고 게시판에 글 하나 올렸습니다.

temp 7년 전 0

아.. 답이 0이될거라고는 깊게 생각안해봤었네요 ㅎㅎ

어쩐지..수많은 경우를 돌려봐도 분명 틀릴게없다고 생각했고, 정답소스가 뭔가 이상하다고 생각하고있었습니다.

아무쪼록 테스트케이스 허점을 찾아내신 집념이 대단하신하시네요 ㅎㅎ

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

문제

문제

출처

ICPC

오답반례 질문입니다. 이건 맞는거아닌가요?

temp 7년 전 0

temp 7년 전 0

simm4256 7년 전 0

temp 7년 전 0

simm4256 7년 전 0

temp 7년 전 0

simm4256 7년 전 0

temp 7년 전 0

simm4256 7년 전 1

simm4256 7년 전 0

temp 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말