글 읽기 - 왜 틀리는지 모르겠습니다..

wjo0204 2년 전 0

직접 n*n 배열을 생성해서 정렬하고 하나하나 비교하는 코드로 테스트를 해 봐도

n=300까지는 모두 맞는 걸 확인했는데, 계속 오답이라 하네요.

코드상의 문제점이나 아니면 반례 하나라도 알려주시면 감사하겠습니다.

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

using namespace std;

int n, k;

long long cnt_less(int target) {
	long long cnt = 0;
	for (int i = 1; i <= n; ++i) {
		cnt += min(n, target / i);
	}
	return cnt;
}

int getKth() {
	int low = 1, mid, high = int(min((long long)n * n, 100000000LL)) + 1;
	while (low < high) {
		mid = (low + high) / 2;
		long long cnt = cnt_less(mid);

		if (cnt < k) low = mid + 1;
		else high = mid;
	}
	return low;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	cout << getKth() << endl;
	return 0;
}

circlezer0 2년 전 4

100000
1000000000

output : 100000001

ans : 204535821

wjo0204 2년 전 1

아 감사합니다.

제가 자리수를 잘못봤군요

n이 최대일때도 테스트를해보고 싶었는데, 64bit 모드로 돌려도 n*n 배열 할당하다가 프로그램이 죽어버려서 테스트를 못했거든요.

오타를 주의하자는 교훈 하나 또 배우고 갑니다.

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

문제

문제

출처

ICPC

왜 틀리는지 모르겠습니다..

wjo0204 2년 전 0

circlezer0 2년 전 4

wjo0204 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말