글 읽기 - 틀린케이스를 잘 모르겠고.... 문제도 잘 이해가안되요

bsdlcksdn 8년 전 0

이분탐색? 으로 풀려고 해서 나름 짜봤습니다.

도무지 이해가 잘 안되서 질문 올립니다.

질문 게시판에 보니까

4 4

같은 경우에는 답이 1이라고 하시는데;; 2가 되야 맞는거아닌가요??

(이런케이스에는 1이 버려지는겁니까? 1개로 쳐지는 겁니까?? 1개로 쳐지면 2가 맞는것 같은데요;;

그리구 위의 케이스에서 결과가 '2이상의 임의의 값' 이어도 맞는 경우가 아닌가요..?(결과적으론 4개가 나오니....)

다른 예시로

3 6

은 값이 10이라구 하시더라고요.. 이걸보면 또 1을 1개로 쳐서 7개로 만들어서 통과한건지....

1을버리고 6개로 통과한건지 잘 모르겠습니다.

뭘 잘못이해하고 있는건가요..?

#include <iostream>
using namespace std;

int n, k;
int line[10010];
int max_length;
int maxmax=0;
void serach(int start, int end) {

	while (start<=end) {

		int mid = (start + end) / 2;
        
		int count = 0; //랜선개수
		for (int i = 0; i < k; i++) {
            
            //측정값보다 작으면 1개로 침.
			if (mid > line[i])
				count += 1;
			else
				count += (int)(line[i] / mid);
		}
        
		if (mid > maxmax) {
			end = mid - 1;
		}
		else if (count >= n) {
			max_length = mid;
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}


	}

	

}

int main() {

	cin >> k>> n;
	

	for (int i = 0; i < k; i++) {
		cin >> line[i];

		if (line[i] > maxmax)
			maxmax = line[i];
	}

	serach(1, 1000000);

	cout << max_length << endl;

}

bsdlcksdn 8년 전 0

답변 정말 감사합니다. ㅎ;;;

소스를 다음과 같이 바꿔보구.. 웬만한 테스트케이스 돌려봐두 맞게나오는데 틀리다고 하네요. ㅠㅠ

어디가 틀렸는지 힌트를 받을 수 있을까요?

#include <iostream>
using namespace std;

int n, k;
int line[10010];
int max_length;

void serach(int start, int end) {

while (start<=end) {

int mid = (start + end) / 2;

//cout <<"start : "<<start << " /  mid : " << mid << " /  end : "<<end<<endl;

int count = 0;
for (int i = 0; i < k; i++) {
count += (int)(line[i] / mid);
}
if (count >= n && max_length< mid) {
max_length = mid;
start = mid + 1;
}
else {
end = mid - 1;
}

}

}

int main() {

cin >> k>> n;
for (int i = 0; i < k; i++) {
cin >> line[i];
}

serach(1, 1000000);

cout << max_length << endl;

}

bsdlcksdn 8년 전 0

ㅋㅋㅋㅋ;; int line[100010]; 말씀하시는 건가요....? 그래서 long long int로 바꿔봤는데 안되네요;;

안물어보고 풀려고했는데;;; 한 10번넘게틀리니까 빡쳐서 못풀겟어요 ㅠㅠ;

search는 이분탐색이니까 long(n)인가? 그러니까 만*백만이 어디말씀하시는건지를 모르겠네요;;

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

문제

문제

출처

ICPC

틀린케이스를 잘 모르겠고.... 문제도 잘 이해가안되요

bsdlcksdn 8년 전 0

bsdlcksdn 8년 전 0

bsdlcksdn 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말