글 읽기 - 징검다리 질문합니다..

saeugsa_uka 6년 전 0

안녕하세요..

계차수열 공식 쓰고, 이분탐색을 통해 최대로 걷는 징검다리의 수 M을 구했습니다.

M번쨰에 N번째 징검다리에 닿으면 M번이 답이고,

N에 최대한 가까우면서 N보다 작은 징검다리에 도달했을 땐

한번 뒤로 가고 바로 N으로 가면 답이라 생각해서 M-1+1 =M으로 답을 했는데 틀렸다고 나옵니다..

어디서 틀렸을까요...ㅠㅠ

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;



int main() {
	int t;
	cin >> t;
	while (t--) {
		long long n;
		long long ret = 1;
		long long l = 1, r, m;
		cin >> n;
		r = n;
		while (l <= r) {
			m = (l + r) / 2;
			if (m*(m + 1)<= n*2) {
				if (m*(m + 1) == n*2) {
					ret = m;
					break;
				}
				else
					ret = max(ret, m), l = m+1;
			}
			else r = m-1;
		}
		cout << ret << endl;
	}
	return 0;
}

herdson 3년 전 0

사실 이 문제는 long long이 아니라 unsigned long long으로 풀립니다.

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

문제

문제

출처

ICPC

징검다리 질문합니다..

saeugsa_uka 6년 전 0

herdson 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말