글 읽기 - 100퍼센트에서 '틀립니다'가 나옵니다

toojoy 1년 전 0

int 범위 문제인가 싶어서 long long으로 바꿔도 마찬가지더군요.

제가 어디를 잘못 생각하고 있는지 모르겠어서 글 남깁니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int T, N, M;

using ll = long long;

vector<ll> printDummy;
vector<ll> answer;

/*
* 할인 가격은 정상가 보다 항상 낮게 나온다는 걸 전제로 하여 문제를 접근
*/

int main()
{
	
	cin >> T; //테스트 케이스 입력
	
	
	for (int t = 1; t <= T; t++) //해당 테스트 케이스 횟수 만큼 루프
	{
		cin >> N; //N에 대한 입력

		M = 2 * N; //2N을 담을 변수

		for (int i = 0; i < M; i++) //출력더미 가격 입력받는 루프문
		{
			ll temp = 0;
			cin >> temp;
			printDummy.push_back(temp);
		}

		for (int i = 0; i < M; i++)
		{
			ll salePrice = (ll)(printDummy[i] * 0.75); //할인된 가격

			bool bFound = binary_search(printDummy.begin(), printDummy.end(), salePrice); //이진탐색으로 할인된 가격이 존재하는지 체크

			if (bFound == true)
			{
				vector<ll>::iterator low; //lower_bound 이터레이터 변수
				low = lower_bound(printDummy.begin(), printDummy.end(), salePrice);
				int idx = (int)(low - printDummy.begin()); //위치값 계산
				answer.push_back(salePrice); //답을 담을 벡터에 할인가 넣기
				printDummy[idx] = 0; //출력더미 벡터에서 제외시키기
			}
		}

		cout << "Case #" << t <<": ";

		for (int i = 0; i < answer.size(); i++)
			cout << answer[i] << " ";

		cout << "\n";

		printDummy.clear();
		answer.clear();
	}
	
	

	return 0;
}

logicdrive 1년 전 1

38 ~ 52 번째 줄을 보시면 정상가에서 할인된 가격을 구하고, 그것이 존재할 경우 답에 추가하고, 할인된 가격이 제외되도록 0으로 초기화하고 있습니다.

하지만, 여기서 사용된 정상가는 0으로 초기화되지 않고 있어서 추후 검색시에 할인가로 잘못인식될 수 있습니다.

물론, 99%의 테스트 데이터에서는 이러한 문제는 드러나지 않습니다.

여기에 대한 반례를 위해서는 테스트 데이터를 저격하는 방식으로 만들어야 합니다.

이에 대한 반례를 제시해드립니다.

반례 >
입력값
1
2
27 36 48 64

출력값
Case #1: 27 36 48

기대값
Case #1: 27 48

toojoy 1년 전 0

말씀해주신대로 처음부터 차근차근해서 풀었습니다. 감사합니다.

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

문제

문제

출처

ICPC

100퍼센트에서 '틀립니다'가 나옵니다

toojoy 1년 전 0

logicdrive 1년 전 1

toojoy 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말