문제 링크 : https://www.acmicpc.net/problem/1011
문제 풀이
이 문제는 초기 위치에서 시작해, 이전 변위와 현재 변위의 차가 1 이하가 되도록 이동하여, 마지막 위치까지 이동했을 때 이동 횟수의 최솟값을 묻는 문제이다.
i번째 이동에서의 이동거리를 D(i)로 정의해보자. 이제 각각의 이동에 대해 D(i)를 최대로 할 수 있게 Greedy방법을 써보자.
현재 위치 current에 대해 D(i)로 이동하려면
(a) 남아있는 거리 d는 적어도 1 + 2 + ... + D[i]-1보다는 커야한다.
조건 (a) 를 만족해야함이 자명하다(변위는 1씩 감소할 수 있는데 마지막에 변위가 1로 끝나야하므로) . 또, D(i)는 이전 변위 D(i-1)에 의해서 결정되는데, 둘의 차이는 항상 1보다 작거나 같다. 따라서 d의 범위에 따라 D(i-1)을 이용해서 D(i)를 정해주면 나머지도 귀납적으로 정의가 될 것이다.
Case 1) | current와 y의 거리 | = d + D(i) ≥ 1 + 2 + .. + D(i-1) + (D(i-1) + 1)
D(i) = D(i-1) + 1이 되어도 조건 (a) 를 만족하므로 D(i) = D(i-1) + 1가 되는 것이 가장 유리하다.
Case 2)|current와 y의 거리| = d + D(i) ≥ 1 + 2 + .. + D(i-1)
D(i) = D(i-1) + 1인 경우는 조건 (a) 를 만족하지 않고 D(i) = D(i-1)까지만 조건을 만족하므로 D(i) = D(i-1)인 경우가 가장 유리하다.
Case 3) elsewise
D(i)는 D(i-1) - 1이 될 수 밖에 없다.
코드
#include <iostream>
using namespace std;
int main()
{
int T,x0,y0;
cin>>T;
while(T--)
{
cin>>x0>>y0;
int delta=0,current=x0,sum=1,n=0;
while(current != y0)
{
n++;
if(y0-current>=sum)
{
delta ++;
current += delta;
sum += delta + 1;
}
else if(y0-current >= sum - delta-1)
{
current += delta;
}
else
{
sum -= delta + 1;
delta --;
current += delta;
}
}
cout<<n<<"\n";
}
}
y0 - current = |current와y의 거리|
n = |이동 횟수|
delta = D(i)
x0 = |초기위치|, y0 = |목표 위치|
T = |테스트 케이스|
'정보 > 백준 문제풀이' 카테고리의 다른 글
백준 8983번 사냥꾼 C++ (0) | 2024.03.19 |
---|---|
백준 10166번 관중석 C++ (0) | 2024.03.19 |
백준 1654번 랜선 자르기 C++ 이분탐색 (0) | 2024.01.27 |
백준 1713번 후보 추천하기 C++ (1) | 2024.01.06 |
백준 2628번 종이자르기 C++ (1) | 2023.12.23 |