글 읽기 - 힌트를 얻을 수 있을까요?

tmd3283 5년 전 0

구간을 설정하고 구간의 길이를 토대로 bisection으로 풀었는데요

구간의 시작이 마지막 값을 제외하면 오름차순으로 되어 있어서 가장 먼저 target의 길이를 넘어서는 구간이 있다면 바로 cnt++로 세주고

구간을 다음 것으로 갱신했습니다. 그렇지 않으면 끝부분만 늘려서 구간의 길이를 증가시켰고요.

K==1이면 전체 길이로 예외처리 했구요. 어디서 틀렸는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
using lint = long long;
using ii = pair<int, int>;

const int INF = 987654321;
int N, K,M;
vector<int>vec;
vector<ii>range;
bool decision(int size) {
	int cnt = 0, s = range[0].first, e = range[0].second;
	int idx = 0;
	while (idx < range.size()) {
		//구간의 길이
		int len = (e - s + N) % N ;
		//구간이 size보다 같거나 길다면 다음 것으로 갱신
		if (len >= size) {
			s = range[(idx + 1) % M].first;
			e = range[(idx + 1) % M].second;
			cnt++;
		}
		else {
			//그렇지 않다면 끝 부분만 늘린다.
			e = range[(idx + 1) % M].second;
		}
		idx++;
	}
	return (cnt >= K);
}
int main(void) {
	scanf("%d%d%d", &N,&M, &K);
	vec = vector<int>(M);
	for (int i = 0; i < M; i++) {
		scanf("%d", &vec[i]);
	}
	//한 겹만 필요할 때는 N출력하고 끝내기.
	if (K == 1) {
		printf("%d\n", N);
		return 0;
	}
	for (int i = 0; i < M; i++) {
		range.push_back(ii(vec[i], vec[(i + 1) % M]));
	}
	int lo = -1, hi = N + 1;
	//lo는 반드시 되며 hi=lo+1까지 실행하고 hi일 때는 되지 않는다.
	while (lo + 1 < hi) {
		int mid = (lo + hi) >> 1;
		//mid의 크기로 절단 할 수 있다면 lo를 갱신.
		if (decision(mid))
			lo = mid;
		else
			hi = mid;
	}
	printf("%d\n", lo);
	return 0;
}

nsj6646 5년 전 0

시작을 항상 첫번째 절단지점에서만 시작하시는데요.

절단은 어느 지점에서나 시작할 수 있습니다.

문제의 예제로 예를 들면 절단의 시작지점을 2가 아닌 4나 6에서 시작할 수도 있습니다.

그 부분만 추가하시면 통과하실 것 같습니다.

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

문제

문제

출처

ICPC

힌트를 얻을 수 있을까요?

tmd3283 5년 전 0

nsj6646 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말