[Python] 백준 16218번 - 힘 겨루기 (실버 4) (ValueError !!!)

혼자 힘으로 풀었는가? 몰라이씨

알고리즘 분류
 - 구현
 - 수학
 - 그리디 알고리즘

 

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

 

문제

서기 2045년, 세상은 어마무시하게 발전해서 엄청나게 힘이 강한 AI가 널리 보급되었다. 헬스를 열심히 하던 junie는 자신의 힘을 확인하기 위해서 코드네임 “TEST_SUBJECT_107”과 힘 겨루기를 하기로 했다.

힘 겨루기는 총 N개의 라운드로 구성되어있고, i라운드에 junie는 Ai의 힘을, TEST_SUBJECT_107는 Bi의 힘을 준다. 둘 다 K 이상의 힘을 버티지 못하기 때문에 지금까지 준 힘 (누적힘)이 K보다 크거나 같아지면 상대가 타격을 받고 게임이 종료된다. 또한 junie가 TEST_SUBJECT_107보다 많은 누적힘을 주고 그 차이가 50 이상이 되면 인간의 고등한 능력을 사용한 한판승으로 게임이 끝난다. 힘 겨루기의 승자는 후술할 규칙에 따라 결정된다.

junie는 TEST_SUBJECT_107를 못 이긴다는 생각에 비장의 필살기 "OverPower"를 준비했다. 이 필살기는 한 번만 사용할 수 있고, i번째 라운드에서 사용하면 junie가 Ai 대신 1.5Ai의 힘을 줄 수 있다. 그 값이 정수가 아닐 경우 정수로 버림한다. 하지만 이 필살기에는 부작용이 있어서, junie가 추가로 준 힘의 양만큼 다음 라운드에서 힘이 빠지게 된다. 그 결과로 음수의 힘을 줄 수도 있으며, 이것도 누적힘에 반영된다.

예를 들어서, 첫 번째 라운드에 10, 두 번째 라운드에 18의 힘을 주고, 첫 번째 라운드에서 OverPower를 사용한다고 하자. 그러면 첫 번째 라운드에서 15의 힘을 주고, 두 번째 라운드에서 5의 힘을 뺀 13의 힘을 주게 된다.

힘 겨루기의 승자는 다음과 같이 결정된다. 한 쪽만 상대에게 타격을 주었을 경우 그 쪽이 승리한다. 두 선수가 동시에 타격을 받으면 OverPower의 사용 유무에 따라 승패가 달라진다. OverPower를 사용했을 경우 TEST_SUBJECT_107의 승리가 되며, 사용하지 않았을 경우 junie의 승리가 된다. 두 선수가 동시에 타격을 받지 않고 한판승으로 게임이 끝날 경우 junie가 승리한다. N라운드가 끝날 때까지 아무도 타격을 주지 않고 한판승도 일어나지 않으면 무승부로 끝난다.

junie는 너무 똑똑해서 어떻게든 지지 않으려고 한다. 각 라운드마다 junie와 TEST_SUBJECT_107이 주는 힘이 주어질 때, 과연 힘 겨루기의 승자는 누가 될까?

메모리 제한에 유의하라.

입력

N(1 ≤ ​​​​​​N ≤ 400000)과 K(100 ≤ K ≤ 1000)이 주어진다

다음 줄부터 N개의 줄에 junie와 TEST_SUBJECT_107의 힘이 주어진다. 모든 힘은 0 이상 60 이하이다.

출력

최종 승리자의 숫자를 출력한다.

junie의 승리는 1, TEST_SUBJECT_107의 승리는 -1, 무승부는 0을 출력한다.

 

---

문제 자체는 어렵게 느껴질 문제가 아니다.

 

하지만 풀고나서 제출하면 통과가 안된다.

 

우선 문제를 풀기전 내용을 정리하면

 

1. k 이상일때 승리
2. sumA가 sumB보다 50이상이면 a승리
3. op는 1.5 (소수점버림), 다음에 1.5만큼 차감
4. 타격하면 승리
5. 둘이 동시에 타격받으면 op사용유무에 따라
    5-1. op사용시 b승리
    5-2. op미사용시 a승리
6. 타격받지않고 한판승으로 끝나면 a승리 (2와 같음)
7. n라운드가 끝날대가지 타격x 한판승x이면 무승부
한판승 = 50점이상
타격 = k 이상
op 사용조건 = 현재 라운드에서 1.5의 힘을 더줫을때 50을 넘길수 잇거나 k이상이 될 때

 

위와 같이 정리할 수 있다.

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

sumA = 0
sumB = 0
res  = 0
op = False

for _ in range(n):
    a, b = map(int, input().split())

    if res != 0:
        continue

    sumB += b
    opA = a * 15 // 10
    tmpA = sumA + opA

    if (not op) and sumB < k and (tmpA >= k or tmpA >= sumB + 50):
        sumA = tmpA
        op = True
    else:
        sumA += a

    if sumA >= k and sumB >= k:
        if op:
            res = -1
        else:
            res = 1
    elif sumA >= k:
        res = 1
    elif sumB >= k:
        res = -1
    elif sumA >= sumB + 50:
        res = 1

print(res)

 

그리고 위의 설명을 그대로 구현한 문제다.

 

제출하면 ValueError를 볼 수 있다.

 

문제를 제출할 때마다 다른 %에서 발생되며 난 백준의 문제가 랜덤성인지 한번 의심하는 계기가 되었다.

 

무수히 많은 ValueError

 

그래서 위의 맞았습니다!! 두개는 뭐냐?

 

입력방식 자체를 수정해서 제출했다.

 

import sys

data = sys.stdin.buffer.read()
L = len(data)
idx = 0

def next_int():
    global idx
    while idx < L and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < L and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

n = next_int()
k = next_int()

sumA = 0
sumB = 0
res = 0
op = False

for _ in range(n):
    a = next_int()
    b = next_int()

    if res != 0:
        continue

    sumB += b
    opA = a * 15 // 10
    tmpA = sumA + opA

    if (not op) and (sumB < k) and (tmpA >= k or tmpA >= sumB + 50):
        sumA = tmpA
        op = True
    else:
        sumA += a

    if sumA >= k and sumB >= k:
        res = -1 if op else 1
    elif sumA >= k:
        res = 1
    elif sumB >= k:
        res = -1
    elif sumA >= sumB + 50:
        res = 1

sys.stdout.write(str(res))

 

이제서야 문제가 풀렸다.