말씀하신대로 입력될 수 있는 값의 범위가 매우 커서(0~10억)
극단적인 경우의 입력이 주어졌을 경우, 작성하신 솔루션(Y++; X++;)으로는 제한시간 안에 통과할 수 없을것 같네요..
연산 횟수를 줄일 수 있는 다른 방법을 생각해봐야 될 것 같습니당
1072번 - 게임
...
가만보니 시간초과를 어떻게 하면 벗어날 수 있을지가 질문이었는데
질문을 고대로 제가 다시 읊어드린 겪이네요 ㅎ, ㅎ...
바로 힌트를 드리는게 도움이 될 지 모르겠지만
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
댓글을 작성하려면 로그인해야 합니다.
kokorin 7년 전 1
값이 커서 98%->99%
올라가는데 값이 많이 필요할 것같은 느낌은 알겠는데
어떻게 시간초과의 굴레에서 벗어날 수 있을 까여??ㅜㅠ