[백준] Fly me to the Alpha Centauri

 

 

---

 

 

---

 

문제

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

 

 

개념

수학

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    long long x, y;
    cin >> x >> y;

    double dist = y - x;                // 거리
    double dist_sqrt = sqrt(dist);      // 거리 제곱근
    int dist_round = round(dist_sqrt);  // 반올림

    if (dist_sqrt <= dist_round)
      cout << dist_round * 2 - 1 << '\n';
    else
      cout << dist_round * 2 << '\n';
  }

  return 0;
}

 

 

 

 

코드 설명

구현은 간단하지만 패턴을 알아내는 것이 어려운 문제였다.

처음에는 dp로 풀려고 했으나 마지막의 이동 횟수가 1이라고 해서 당황했다..

일단 처음과 마지막 이동횟수는 무조건 1이라는 정보는 명확하므로 이에 따라 거리를 늘려가면서 거리 당 이동 횟수를 노가다로 구해보며 수학적인 패턴을 찾는다.

 

출처: https://jaynamm.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1011%EB%B2%88-Fly-me-to-the-Alpha-Centauri

 

 

두 지점간의 거리에 따른 각 이동 횟수는 위 표와 같다.

거리는 시작 지점부터 마지막 지점까지의 사이이므로 y - x 이다.

 

해당 거리의 제곱근값인 dist_sqrt를와, 이를 반올림한 값인 dist_round를 정의한다.

두 값이 필요한 이유는 dist_round가 어느 쪽에 가까운지에 따라 이동횟수가 결정되기 때문이다. 

 

두 값을 비교하여 만약 dist_sqrt가 dist_round보다 작거나 같은지를 비교하여 

참이라면 2 * 반올림 값 - 1, 아니라면 2 * 반올림 값을 출력한다.

 

---