akssus   2년 전

수학적으로 안하고 DP같이 풀었는데요

숫자 각 자리를 돌면서 1을 더할 수 있는지 검사하고 가능하면 +1 하고

배열 끝까지 +1이 불가능하면 배열 마지막에 1을 푸시합니다

예를 들면 111에선 중간 1에 1을 더할 수 있으므로 121이 되고,

121은 더이상 1을 더할 수 있는 값이 없으므로 1211로 만들고.. 이걸 

합이 d와 같아질때까지 반복합니다... 이러면 루트까지 알 수 이

이런 아이디어로 만들어봤는데

시간초과가 떠서

먼저 최대속력을 구해서( v^2 < d를 만족하는 v의 최대값)

대칭 배열 123...v...321을 만든다음 위 과정을 반복하는 식으로

연산 수를 좀 줄여봤지만.. 그래도 시간초과네요

좋은 방법 있을까요?


chogahui05   2년 전

이거 좀 어렵죠.. 생각 외로 타임 아웃이 많이 나는 문젠데..

브루트 포스하게 접근하면 그런 듯 싶네요.

이럴 경우에는 규칙을 찾아봅시다.


이동해야 할 거리를 d라고 해 봅시다. 그리고 최적으로 1, 2, 3, ..., x칸씩 이동한다고 가정해 보죠.

그러면 x(x+1)/2 = d/2잖아요. x(x+1) - d = 0임을 알 수 있죠.

x^2 + x - d = 0의 해를 먼저 구하면 좋지 않을까요?

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