글 읽기 - 50% 에서 시간초과아...

saera1111 6년 전 0

어떻게 해결해야될지 감이 전혀 안오네요..

아예 다른 접근 방법으로 구현을 해야 하는 걸까요?

ㅠㅠㅜㅜㅠ답변 부탁드립니다 고수님들

#include <iostream>
#include <vector>
using namespace std;

int main() {
	long long T, x, y;
	long long distance, left_dis, went_dis = 0;
	int max_vel = 2;

	//테스트 케이스 수 입력
	cin >> T;
	vector<int> result(T, 0);

	for (int i = 0; i < T; i++) {
		cin >> x >> y;
		distance = y - x;
		left_dis = distance;

		//거리가 3 이하
		if (distance <= 3) {
			result[i] = distance;
			continue;
		}
		// 거리가 4 이상일 경우
		//최대 이동 속도 계산(max_vel)
		while (1) {
			if (distance < (max_vel + 1) * (max_vel + 1)) {
				result[i] = max_vel;
				break;
			}
			max_vel++;
		}

		//1. 거리가 max_vel값의 제곱일 경우
		if (distance == max_vel*max_vel) {
			result[i] = max_vel * 2 - 1;
			continue;
		}

		//2. 그 외의 경우
		//남은 거리와 최대 속도를 도달했을때 까지 간 거리 구하기
		for (int i = 1; i <= max_vel; i++) {
			left_dis -= i;
			went_dis += i;
		}
		//남은 거리 내 최소의 이동횟수 구하기
		while (left_dis) {
			if (left_dis >= went_dis) {
				left_dis -= max_vel;
			}
			else {
				went_dis -= max_vel;

				if (max_vel > 1)
					max_vel--;
				left_dis -= max_vel;
			}

			result[i]++;
		}

	}


	for (int i = 0; i < T; i++) {
		cout << result[i] << endl;
	}



	return 0;
}

jh05013 6년 전 1

질문 검색을 누르면 반례가 많이 나옵니다.

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

문제

문제

출처

ICPC

50% 에서 시간초과아...

saera1111 6년 전 0

jh05013 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말