이거 좀 어렵죠.. 생각 외로 타임 아웃이 많이 나는 문젠데..
브루트 포스하게 접근하면 그런 듯 싶네요.
이럴 경우에는 규칙을 찾아봅시다.
이동해야 할 거리를 d라고 해 봅시다. 그리고 최적으로 1, 2, 3, ..., x칸씩 이동한다고 가정해 보죠.
그러면 x(x+1)/2 = d/2잖아요. x(x+1) - d = 0임을 알 수 있죠.
x^2 + x - d = 0의 해를 먼저 구하면 좋지 않을까요?
1011번 - Fly me to the Alpha Centauri
이거 좀 어렵죠.. 생각 외로 타임 아웃이 많이 나는 문젠데..
브루트 포스하게 접근하면 그런 듯 싶네요.
이럴 경우에는 규칙을 찾아봅시다.
이동해야 할 거리를 d라고 해 봅시다. 그리고 최적으로 1, 2, 3, ..., x칸씩 이동한다고 가정해 보죠.
그러면 x(x+1)/2 = d/2잖아요. x(x+1) - d = 0임을 알 수 있죠.
x^2 + x - d = 0의 해를 먼저 구하면 좋지 않을까요?
댓글을 작성하려면 로그인해야 합니다.
akssus 7년 전
수학적으로 안하고 DP같이 풀었는데요
숫자 각 자리를 돌면서 1을 더할 수 있는지 검사하고 가능하면 +1 하고
배열 끝까지 +1이 불가능하면 배열 마지막에 1을 푸시합니다
예를 들면 111에선 중간 1에 1을 더할 수 있으므로 121이 되고,
121은 더이상 1을 더할 수 있는 값이 없으므로 1211로 만들고.. 이걸
합이 d와 같아질때까지 반복합니다... 이러면 루트까지 알 수 이
이런 아이디어로 만들어봤는데
시간초과가 떠서
먼저 최대속력을 구해서( v^2 < d를 만족하는 v의 최대값)
대칭 배열 123...v...321을 만든다음 위 과정을 반복하는 식으로
연산 수를 좀 줄여봤지만.. 그래도 시간초과네요
좋은 방법 있을까요?