두 친구가 만날 때 최소 피로도를 구하는 C++ 코드

문제 설명

두 개의 숫자 a와 b가 주어지고, 두 명의 친구가 OX 축 위의 위치 x = a와 x = b에 각각 서 있다고 가정해 봅시다. 각 친구는 직선을 따라 어느 방향으로든 한 칸씩 무제한으로 이동할 수 있습니다. 이동할 때마다 피로도는 다음 규칙에 따라 증가합니다. 첫 번째 이동은 피로도를 1만큼, 두 번째 이동은 2만큼 증가시키는 식으로, n번째 이동은 피로도를 n만큼 올립니다. 두 친구는 OX 축 위의 한 정수 좌표에서 만나고자 하며, 이때 두 사람이 얻게 되는 총 피로도의 최솟값을 구해야 합니다.

예를 들어 입력이 a = 5, b = 10이라면 출력은 9가 됩니다. 최적의 방법 중 하나는 다음과 같습니다. 첫 번째 친구는 오른쪽으로 세 걸음, 두 번째 친구는 왼쪽으로 두 걸음 이동합니다. 이때 총 피로도는 1 + 2 + 3 + 1 + 2 = 9가 됩니다.

접근 방법

이 문제의 핵심은 n번 이동했을 때의 피로도가 1부터 n까지의 합, 즉 n(n+1)/2라는 점입니다. 두 사람 사이의 거리를 d라고 할 때, 총 피로도를 최소화하려면 두 사람이 이동하는 거리를 최대한 균등하게 나누어야 합니다. 거리가 짝수일 때는 두 사람이 정확히 절반씩 이동하고, 홀수일 때는 한 사람이 한 걸음 더 이동하게 됩니다.

이를 위해 다음 단계를 따릅니다 −

ans := |a - b|
sum := ans / 2
return (sum + (ans mod 2)) * (sum + 1)

예제

아래 구현을 통해 더 자세히 이해해 봅시다 −

#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b){
   int ans = abs(a - b);
   int sum = ans / 2;
   return (sum + (ans % 2)) * (sum + 1);
}
int main(){
   int a = 5;
   int b = 10;
   cout << solve(a, b) << endl;
}

입력

5, 10