안녕하세요.
여행벌입니다.
오늘은 예전부터 도전했으나.. 계속 실패를 하다 최근에 푼 백준 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 |