[백준 32068번] 보물 찾기

문제 링크

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

 

문제 요약

이 문제는 시작점 \(S\)에서 출발하여 보물 위치 \(L\) 또는 \(R\)에 방문하는데 필요한 이동 횟수를 계산하는 것이다. 이동 패턴은 한 단계식 오른쪽과 왼쪽을 번갈아가며 한 칸씩 점점 더 멀리 이동하는 방식이다.

 

문제 풀이

서브태스크 4번까지는 입력 제한이 크지 않아 시뮬레이션으로도 해결할 수 있다. 그러나 서브태스크 5번을 해결하려면 더 효율적인 접근 방법이 필요하다.

 

먼저, \(S\)보다 왼쪽에 있는 \(L\)을 방문하기 위해서는 \(S\)와 \(L\)의 거리만큼 떨어진 오른쪽에 있는 점들을 모두 방문해야 한다. 따라서 \(L\)을 방문하기 위한 이동 횟수는 \(2 \times (S - L)\)이다.

 

마찬가지로, \(S\)보다 오른쪽에 있는 \(R\)을 방문하기 위해서는 \(S\)와 \(R\)의 거리보다 1만큼 작은 거리에 떨어진 왼쪽의 모든 점들을 방문해야 한다. 따라서 \(R\)을 방문하기 위한 이동 횟수는 \(2 \times (R - S - 1)\)이다.

 

이 놀이는 \(L\)또는 \(R\)을 방문하면 끝난다. 따라서 두 값 중 작은 값이 정답이 된다. 아무것도 하지 않은 초기 상태도 이동 횟수에 포함되므로 최종적으로 1을 더해 출력해야 한다.

 

소스 코드

#include <stdio.h>

int t;

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &t);
    
    while (t--) {
        int l, r, s;
        scanf("%d%d%d", &l, &r, &s);
        
        int left = (s - l) * 2;
        int right = (r - s - 1) * 2 + 1;
        int ans = left < right ? left : right;
        
        printf("%d\n", ans + 1);
    }
}