글 읽기 - 수퍼마리오 반례 좀 들어주세요..

npole0103 4년 전 0

안녕하세요. 수퍼마리오 문제를 풀다가 도저히 모르겠어서 질문드립니다.

모든 경우의 수를 다 적었다고 생각하고 테스트 케이스도 많이 넣어봤는데도 틀렸다고 뜨네요.

제가 생각한 경우의 수는 다음과 같습니다.

1) 총합이 100을 넘지 않았을 경우 -> 총합 출력

2) 현재 sum이 다음 sum보다 100에 가까울 때 -> 현재 sum 출력

3) 다음 sum이 현재 sum보다 100에 가까울 때 -> continue;

4) 현재 sum과 다음 sum이 100에 동일하게 가까울 떄 -> ex)104, 96 다음 sum인 104 출력

이 같은 경우의 수 4가지를 고려하여 코드를 짰는데 틀렸다고 하네요.

혹시 제 코드에 논리적 오류가 있거나, 생각하지 못한 경우의 수가 있다면 지적 부탁드립니다.

감사합니다.

#include <iostream> //수퍼마리오
#include <math.h>
using namespace std;

int main()
{
	int mushroom[10];
	int sum = 0;
	int check = 0;
	
	for(int i = 0; i < 10 ; i++)
		cin >> mushroom[i];
	
	for(int i = 0 ; i < 10 ; i++) //총합이 100이 넘지 않을 때 확인용
		check += mushroom[i];
	
	for(int i = 0 ; i < 9 ; i++)
	{
		sum += mushroom[i];
		//cout << sum << endl;
		
		if( check == sum + mushroom[i+1] && sum + mushroom[i+1] <= 100) //총합이 100을 안 넘을 때
			cout << sum + mushroom[i+1] << endl;
		else if( abs(100 - sum) < abs(100 - (sum + mushroom[i+1])) ) //현재 sum이 100에 더 가까울 때
		{
			cout << sum << endl;
			break;
		}
		else if( abs(100 - sum) == abs(100 - (sum +mushroom[i+1])) ) //다음 sum과 현재 sum이 100에 동일하게 가까울 때
		{
			cout << sum + mushroom[i+1] << endl;
			break;
		}
	
		else if( abs(100 - sum) > abs(100 - (sum + mushroom[i+1])) ) //다음 sum이 100에 더 가까울 때
			continue;
	}
	
	return 0;
}

eve8108 4년 전 2

반례로 10 10 10 10 10 10 10 10 10 19 넣어보세요.

eve8108 4년 전 1

작성자님의 코드는 현재까지의 버섯의 합과 다음 버섯이 더해졌을 경우를 비교하며 진행되게 됩니다.

위의 반례는 i == 8인 경우, 현재까지의 합은 90, 다음 버섯까지의 합은 109

총 합이 100을 넘기때문에 첫번째 조건은 false;

현재 sum 이 100에 더 가까운것이 아니기 때문에 두번째 조건도 false;

다음 sum과 현재 sum이 모두 100이 아니기 때문에 세번째 조건도 false;

다음 sum이 100에 더 가깝기 때문에 네번째 조건은 true, 하지만 i ==9 가 되는 동시에 for문을 빠져나오기 때문에 아무것도 출력하지 않게 됩니다.

이를 방지하기 위해서 밑에 조건을 하나 추가하였습니다.

#include <iostream> //수퍼마리오
#include <math.h>
using namespace std;

int main()
{
	int mushroom[10];
	int sum = 0;
	int check = 0;

	for (int i = 0; i < 10; i++)
		cin >> mushroom[i];

	for (int i = 0; i < 10; i++) //총합이 100이 넘지 않을 때 확인용
		check += mushroom[i];

	for (int i = 0; i < 9; i++)
	{
		sum += mushroom[i];
		
		if (check == sum + mushroom[i + 1] && sum + mushroom[i + 1] <= 100) //총합이 100을 안 넘을 때
		{
			cout << sum + mushroom[i + 1] << endl;
		}
		else if (abs(100 - sum) < abs(100 - (sum + mushroom[i + 1]))) //현재 sum이 100에 더 가까울 때
		{
			cout << sum << endl;
			break;
		}
		else if (abs(100 - sum) == abs(100 - (sum + mushroom[i + 1]))) //다음 sum과 현재 sum이 100에 동일하게 가까울 때
		{
			cout << sum + mushroom[i + 1] << endl;
			break;
		}
		else if (abs(100 - sum) > abs(100 - (sum + mushroom[i + 1])) && i < 8) //다음 sum이 100에 더 가까울 때
		{                                                                      
			continue;
		}
		else {                                                                 
			cout << sum + mushroom[i + 1] << endl;
		}
	}

	return 0;
}

npole0103 4년 전 2

eve8108님

2시간 동안 끙끙대며 고민하다 도저히 반례를 찾을 수 없어서 이렇게 올렸는데,

제가 원하는 형식의 답변을 해주시고, 논리적 오류까지 지적해주셔서 정말 감사합니다.

님이 올려주신 반례는 상상도 못하고 있었네요.

반례를 바로 찾아내신 것도 정말 대단하신 거 같습니다.

이 글을 보실 지 모르겠지만 정말 감사드린다고 전해드리고 싶습니다.

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

문제

문제

출처

ICPC

수퍼마리오 반례 좀 들어주세요..

npole0103 4년 전 0

eve8108 4년 전 2

eve8108 4년 전 1

npole0103 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말