#BOJ19592

장난감 경주

개인적으로 처음 문제를 보고 이해를 잘못한 것이 이 문제를 바로 해결하지 못하고 틀렸습니다.를 여러번 받게 한 이유일 것 같다. 기본적으로 이 문제들을 풀어나가는 이유가 코드잼에서 안정적으로 70점을 획득하기 위한것에 있다는 것을 고려하면 좋지 않은 신호라고 생각한다. 우선 처음 1초간만 이동하는 것이라는 생각을 하지 못했어서 예시들을 이해하지 못했고, 종이에 안 써버릇 하다 보니 그냥 머리로만 풀려 해서 오래 걸렸던 것 같다. 난이도 자체는 실버5가 맞는 것 같은데 난이도를 끄고 문제를 푸는 연습을 이후 문제부터는 진행해보려고 한다. 아래는 간단한 주석인데 아직 6시가 지나지 않아서(일본 가서 제출하려고 아껴놓고 있는거긴 한데) 제출은 아직 해보지 않았다. 그래도 기본적인 논리와 머리 속에 떠오르는 엣지 케이스를 조금 적어보았다.

3 12 11
3 3 3
Output : 4

나의 처음 코드는 실제로 여기서 -1이 출력되는 문제가 있었다. 아래는 고친 코드이고, 풀이의 방향성은 주석에 달아두었다. 문제를 보자마자 시뮬레이션, BF(Brute Force)가 생각나긴 하였다.

import sys

for _ in range(int(sys.stdin.readline())):
    N, X, Y = map(int, sys.stdin.readline().split())
    V = list(map(int, sys.stdin.readline().split()))
    my_speed = V[-1]
    op_speed = max(V[:-1])
    # V[-1]이 최댓값인 경우를 제외하기 위하여 표현
    if my_speed > op_speed:
        print(0)
        continue
        # 내 속도가 상대의 속도보다 빠를 경우

    time1 = X / op_speed
    for i in range(Y, my_speed - 1, -1):
        temp = X
        if (temp - i) / my_speed >= time1 - 1:
            # 조금 귀찮은 작업이었지만 1초의 간극을 수식으로 적었고 부등호를 통해서 공동우승을 유지하였다.
            if i == Y:
                ans = -1
                break
                # 최대치로 뛰었음에도 같거나 더 많이 사용함으로 -1 던지기 위하여 break
            ans = i + 1
            break
    
    print(ans)

그런데 이 코드 조차 5%에서 바로 틀렸습니다가 나와서 왜지 하고 고민을 많이 했다. 반례는 생각보다 간단하였는데 과 동기가 제시해 주었다.

3 12 4
12 1 11
Output : -1

이거 외에도 나눗셈이 주는 불안감이 있어서 곱셈으로 코드를 좀 수정하였다. 수정한 코드는 아래와 같다. 아 근데 진짜 많이 틀렸네... 내 정답률 또륵 ㅜㅜ

import sys

for _ in range(int(sys.stdin.readline())):
    N, X, Y = map(float, sys.stdin.readline().split())
    V = list(map(float, sys.stdin.readline().split()))
    my_speed = V[-1]
    op_speed = max(V[:-1])
    if my_speed > op_speed:
        print(0)
        continue
    time1 = X / op_speed
    ans = -1
    for i in range(int(Y), int(my_speed) - 1, -1):
        temp = X
        if (time1 - 1) * my_speed + i <= X:
            if i == Y:
                ans = -1
                break
            ans = i + 1
            break

    print(ans)