글 읽기 - c++)해결못하신분들 참고하시면 좋을것 같아요

wogus23 4년 전 0

저도 초보인만큼 참고만 해주세요.

BFS로 구현해봤는데 초보라 까다로운 부분이 있어서 수학 카테고리인만큼 수학적으로 해결해봤습니다.

우선 속도상승은 전체 진행과정에서 딱한번만 이루어지고 가속과정이 중단 시점부터는 같은속도or낮은속도로진행 이라는 아이디어로 만들어봤습니다.

max position이 2^31이라서 다른 자료형을 쓰지는 않았구요 물론 구현방법에따라 자료형을 바꿔야 할 수도있습니다.

이해가 안가시는 부분 있으시면 댓글 달아주세요~

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

int up_speed(int dis, int&sp,int&count)
{
	int sum = 0;
	while (dis-sum>=sum+sp+1)//다음속도로 진행가능한지?
	{
		
		sp++;
		sum += sp;
		count++;
	}
	return sum;
	
}
void find_else(int dis, int&sp, int&count,int reserve)
{
	int sum = 0;
	while (1)
	{
		//같은속도로 진행한지
		while (reserve <=dis - sum)
		{
			count++;
			sum += sp;
		}
		//낮은 속도로 진행
		reserve -= sp;
		sp--;
		sum += sp;
		if (sp == 0)
			break;
		count++;
		
		
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int test;
	cin >> test;
	int x, y;
	for (int i = 0; i < test; i++)
	{
		cin >> x >> y;
		int speed = 0;
		int time = 0;
		int r=up_speed(y - x, speed,time);
		
		find_else(y - x-r, speed, time,r);
		cout <<time<<"\n";
	}
	
}

finemini 3년 전 0

도움이 됬습니다. 감사합니다!

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

문제

문제

출처

ICPC

c++)해결못하신분들 참고하시면 좋을것 같아요

wogus23 4년 전 0

finemini 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말