글 읽기 - '틀렸습니다' & 시간초과가 나오네요...

qotndus43 4년 전 0

레고를 정렬하여 이분탐색법을 이용했는데요,
1 2 4 6 13 18 19 23으로 정렬되어있는데 구멍의 길이가 17이라면
하나의 레고(legos[i])를 선택해놓고 다른 레고들 중에서 구멍의 길이가 17 - legos[i]가 되는 레고를 찾는 방식을 이용했는데
아무리 고쳐봐도 틀렸다고 나오길래 톡방에 질문해봅니다 ㅠㅠ
이분탐색 과정에서 오류가 있는걸까요?

수정)

이분탐색법을 재귀가 아니라 while문으로 구현하니 시간초과가 나오네요 ㅠㅠ

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

using namespace std;

long long int binary(vector<long long int> legos, long long int start, long long int end, long long  int x) { // start부터 end까지 x를 찾는 함수
	if (start > end) {
		return -1;
	}

	else if (start == end) {
		if (legos[start] == x)
			return start;
		else
			return -1;
	}

	else {
		if (legos[start] == x) return start;
		else if (legos[end] == x) return end;

		int mid = (start + end) / 2;
		if (legos[mid] == x) return mid;
		else if (legos[mid] < x) {
			binary(legos, mid + 1, end, x);
		}
		else if (legos[mid] > x) {
			binary(legos, start, mid - 1, x);
		}
	}
}

int main() {
	long long int x;
	while (scanf("%lld", &x) == 1) {
		vector<long long int> legos;
		int n;
		int flag = 0;

		long long int l1, l2;

		cin >> n;
		for (int i = 0; i < n; i++) {
			long long int a;
			cin >> a;
			legos.push_back(a);
		}

		x = x * 10000000;
		sort(legos.begin(), legos.end());
		for (int i = 0; i < n - 1; i++) {
			l1 = legos[i];

			long long int idx = binary(legos, i + 1, n - 1, x - l1);
			if (idx != -1) {
				l2 = legos[idx];
				flag = 1;
				break;
			}
		}

		if (flag == 1) {
			cout << "yes " << l1 << ' ' << l2 << endl;
		}
		else {
			cout << "danger" << endl;
		}
	}

	return 0;
}



---------수정 코드------
    #include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

vector<int> legos;

int binary(vector<int> legos, int start, int end, int x) { // start부터 end까지 x를 찾는 함수
	if (legos[start] == x) return start;
	if (legos[start] > x) return -1;
	if (legos[end] == x) return end;
	if (legos[end] < x) return -1;

	while (start + 1 < end) {
		int mid = (start + end) / 2;
		if (legos[mid] == x) return mid;
		else if (legos[mid] < x) {
			start = mid;
		}
		else {
			end = mid;
		}
	}
	return -1;
}

int main() {
	int x, n, flag = 0;
	while (scanf("%d", &x) == 1) { // 구멍의 길이(cm)
		int l1, l2; 
		x = x * 10000000; // 구멍의 길이 cm -> nano miter
		flag = 0;

		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			int a;
			scanf("%d", &a);
			legos.push_back(a);
		}
		sort(legos.begin(), legos.end());
		for (int i = 0; i < n - 1; i++) {
			l1 = legos[i];

			int idx = binary(legos, i + 1, n - 1, x - l1);
			if (idx != -1) {
				l2 = legos[idx];
				flag = 1;
				break;
			}
		}

		if (flag == 1) {
			printf("yes %d %d\n", l1, l2);
		}
		else {
			printf("danger\n");
		}
		legos.clear();
	}

	return 0;
}

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

문제

문제

출처

ICPC

'틀렸습니다' & 시간초과가 나오네요...

qotndus43 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말