BOJ #12934

LEVEL :

Gold5

문제 요약 :

두 선수의 가위바위보의 각 점수를 보고 첫번째 선수가 해당 점수를 가지기위한 최소승리 횟수는?

해결 방안 :

솔직히 이번문제는 다른 골드5문제에 비해서 조금 평이한 수준이었던 것 같다.
두 선수의 총 점수를 알면 총 실행한 가위바위보 턴 수를 알수있다.
각 점수는 해당 턴수 만큼 얻는다. ex) n턴의 승리자는 n점을 얻는다.
따라서 두 선수의 최종 점수의 총 합은 1+2+3+...+n 과 같다.
즉, 등차가 1인 등차수열의 합이니, n(n+1)/2 이다.
근의공식으로 n의 값 즉, 가위바위보 총 실행 횟수를 구한다음, n부터 1까지 반복문을 돌면서 최소 승리횟수를 구하는 문제였다.
두 선수의 총점으로 총 실행 횟수를 구할 수 있다는 생각만 한다면 쉬운 문제였던 것 같다.
시간복잡도는 O(N)이다.

Solution

import sys
import math
input = sys.stdin.readline
if __name__ == "__main__" :
    x,y = map(int,input().strip().split())
    a = 1
    b= 1
    c = -1*2*(x+y)
    if b**2-4*a*c < 0:
        print(-1)
        sys.exit(0)
    turn= max((-b+math.sqrt(b**2-4*a*c))/2*a,(-b-math.sqrt(b**2-4*a*c))/2*a)
    if turn % 1 != 0 :
        print(-1)
        sys.exit(0)
    else :
        turn = int(turn)
    cnt = 0
    s = 0
    for i in range(1,turn+1) : 
        cur = turn+1 - i
        if s == x :
            break
        if s + cur <= x :
            s += cur
            cnt += 1
    print(cnt if s == x else -1)