[백준 32068] 보물 찾기

문제 출처 : https://www.acmicpc.net/problem/32068

보물 찾기(32068)

이 문제는 2024 정보올림피아드 2차 초등부 1번 문제 입니다.

문제 이해하기

S를 중심으로 양쪽으로 한 칸씩 이동하면서 어느쪽 물건을 먼저 찾는지 확인하는 것이 문제입니다. 어렵게 왔다 갔다 하면서 시뮬레이션해야 하는 것 처럼 보이지만 사실 양쪽의 거리만 알면 수학적으로 쉽게 해결 가능합니다.

그래도 일단은 문제에서 요구하는대로 풀어보고, 다음으로 수학적으로 풀어보겠습니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

T = int(input())

for _ in range(T):
    L, R, S = map(int, input().split())
    print(solve(L, R, S))

먼저 테스트 케이스 T를 입력 받습니다. 다음으로 T번 동안 L, R, S를 입력 받습니다. 그리고 문제를 해결하여 출력하도록 합니다.

시뮬레이션 해보기

먼저 시뮬레이션으로 문제를 해결해 보겠습니다. S를 시작으로 왔다 갔다 하면서 언제 보물을 찾을 수 있을지 확인하는 것입니다.

def solve(l, r, s):
    cnt = 0
    while True:
        if s == l or s == r:
            return cnt
        if cnt % 2 == 1:
            s += cnt
        else:
            s -= cnt
        cnt += 1

먼저 몇 번이나 왔다갔다 하는지 확인할 변수 cnt를 만들어 줍니다. 반복문을 실행해서 s가 l이나 r에 닿으면 cnt 값을 리턴하고 끝나는 로직 입니다. 매 번 cnt 값을 1씩 늘려나가면서 홀 수 번째에는 cnt를 더해주고, 짝 수 번째에는 cnt값을 빼줍니다. 이렇게 하면 로직은 맞지만 시간초과로 100점을 얻을 수 없습니다. 그럼 100점을 받을 수 있는 방법을 알아보겠습니다.

수학 풀이

잘 생각해보면 s를 중심으로 l과 r 중 더 가까운 곳에 먼저 닿을 수 밖에 없습니다. 그리고 도착하는데 걸리는 시간은 왕복으로 양쪽을 왔다 갔다 하니까 실제 거리의 2배가 걸리게 됩니다. 오른쪽을 먼저 탐색하기 때문에 왼쪽에 왔다 갔다 한 거리에 1을 더해주면 바로 결과를 얻을 수 있습니다.

def solve(l, r, s):
    sr = r - s 
    ls = s - l 
    
    ans = 0
    if sr <= ls:
        ans += 2 * sr
    else:
        ans += 2 * ls + 1
        
    return ans

s부터 r까지의 거리 sr과, l부터 s까지의 거리 ls를 구해줍니다. 다음으로 두 거리를 비교해 줍니다. 더 작은쪽이 먼저 닿습니다. 만약 두 거리가 같다면 오른쪽을 먼저 탐색하기 때문에 sr이 먼저 닿습니다. 만약 왼쪽인 ls가 거리가 더 짧다면 왔다 갔다 하기 때문에 1을 더해줍니다. 이렇게 하면 간단하게 시뮬레이션을 하지 않아도 답을 구할 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

T = int(input())

def solve(l, r, s):
    sr = r - s 
    ls = s - l 
    
    ans = 0
    if sr <= ls:
        ans += 2 * sr
    else:
        ans += 2 * ls + 1
        
    return ans

for _ in range(T):
    L, R, S = map(int, input().split())
    print(solve(L, R, S))