안녕하세요.

여행벌입니다.

오늘은 예전부터 도전했으나.. 계속 실패를 하다 최근에 푼 백준 1011번 문제를 다뤄보겠습니다.


https://www.acmicpc.net/problem/1011

 

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을

www.acmicpc.net

[알고리즘설계]

최소한이 점프 횟수로 도착해야 되므로, 우리는 점프 길이를 최대한 늘려야 합니다.

하지만, 마지막 점프는 다시 점프 길이 1로 돌아와야 되므로 점프해야 되는 길이 L이 주어졌을 때,

1 2 3 ⋯ N N-1 N-2 ⋯ 1 의 합이 L보다 작은 최대 N을 구해야 됩니다.

등차수열 합 공식을 이용해 보면 1 2 3 ⋯ N N-1 N-2 ⋯ 1 의 합은 N^2이 됩니다.

이때, 남은 L - N^2는 1 2 3 ⋯ N 으로 올라가는 과정에서 1 ~ N 길이의 점프가 다 가능하므로

가장 큰 N부터 점프 횟수를 추가해가며 남은 길이를 처리할 수 있습니다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		long long x, y, length, point, count = 0;
		cin >> x >> y;
		length = y - x;
		if (length <= 3) {
			cout << length << '\n';
			continue;
		}
		for (point = 2; ; point++) {
			if (point * point > length) {
				point--;
				break;
			}
		}

		length -= point * point;
		count += 2 * point - 1;
		while (length != 0) {
			count += (length / point);
			length -= (length / point) * point;
			point--;
		}
		cout << count << '\n';
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1002 - 터렛  (0) 2019.08.21
[BOJ] 17174 - 전체 계산 횟수  (0) 2019.08.21
[BOJ] 1436 - 영화감독 숌  (0) 2019.08.21
[BOJ] 2456 - 나는 학습회장이다.  (0) 2019.08.21
[BOJ] 2579 - 계단 오르기  (0) 2019.08.21

+ Recent posts