kokorin   7년 전

값이 커서 98%->99%

올라가는데 값이 많이 필요할 것같은 느낌은 알겠는데

어떻게 시간초과의 굴레에서 벗어날 수 있을 까여??ㅜㅠ

Hibbah   7년 전

말씀하신대로 입력될 수 있는 값의 범위가 매우 커서(0~10억)

극단적인 경우의 입력이 주어졌을 경우, 작성하신 솔루션(Y++; X++;)으로는 제한시간 안에 통과할 수 없을것 같네요..

연산 횟수를 줄일 수 있는 다른 방법을 생각해봐야 될 것 같습니당

kokorin   7년 전

새로운 방법으로 다시 접근해봐야 될 것 같네여 ㅠㅠ

Hibbah   7년 전

...

가만보니 시간초과를 어떻게 하면 벗어날 수 있을지가 질문이었는데

질문을 고대로 제가 다시 읊어드린 겪이네요 ㅎ, ㅎ...


바로 힌트를 드리는게 도움이 될 지 모르겠지만

parametric search라는 알고리즘이 있습니다.


설명을 드리자면...

A<X<B를 만족하는 X에 대한 함수값 f(X)에 대해, f(X) == T를 만족하는 X를 찾는 효율적인 알고리즘 입니다.

흔히 parametric search를 binary search와 비교를 하는데,

binary search는 N''의 값들 중 특정 값을 빠르게 찾는 알고리즘인데 반해

parametric search는 값은 단 하나인데 해당 값이 가질 수 있는 '범위'가 A~B일 때, 어떤 조건을 만족시키는 특정 값을 빠르게 찾는 알고리즘 입니다.

binary search에서 배열 내의 원소들이 반드시 정렬되어 있어야만 알고리즘을 적용할 수 있듯,

parametric search도 함수 f(X)가 X의 증가에 따라 반드시 단조증가(같거나 증가) 또는 단조감소(같거나 감소) 해야한다는 조건이 있습니다.


질문하신 문제에 빗대어보자면,

f(X) = (현재까지 승수 + X) / (현재까지 게임수 +  X) 로 표현할 수 있겠네요.

문제에서 아주 중요한 조건인.. "앞으로의 게임은 무조건 승리한다."를 적용하면 함수 f는 반드시 단조증가할 수 밖에 없습니다.


여기까지 설명과 binary search의 아이디어를 떠올리면 아마 parametric search의 흐름이 어떤지 어느정도 감이 오실거라 생각됩니다.

구체적인 알고리즘은 검색.....을 통해서 알 수 있을것 같습니다. (익숙해지면 간단한데 처음 짤 때 엄청 어려웠어요....)

사실, 예전에 백준저지에 위키가 있을때 appa님이 잘 정리해주신 자료가 있었는데... 지금 위키글을 찾을 수가 없네요.. (@Baekjoon님 위키 이제 못보나요?)


위 문제 해결하시고 parametric search를 익히는데 도움드리는 차원에서 문제 링크 남겨드릴게요!

parametric search를 적용할 수 있는 문제가 제법 많은데, 솔루션을 알고풀면 실력향상에 큰 도움이 되지 않는것 같아서 두 개만 드립니당

하나는 완전 같은 문제고, 하나는 조금 응용한 문제입니다

https://algospot.com/judge/problem/read/RATIO

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


댓글을 작성하려면 로그인해야 합니다.