전 이렇게 접근했어요
1. 초기엔 감소 연산만 쓴다고 가정하고 답을 n-1로 갱신합니다.
2. 가까운 모든 자연수 제곱수를 a^b = k 꼴로 표현하고 각 자연수 제곱수에 대해서 결과에 |k - n|를 더해줍니다.
32. 다시 a를 n으로 생각하고 1. 연산을 재귀적으로 수행합니다.
참고 1) 단 무작위로 수행하면 시간 초과가 날 것이 뻔합니다. 마치 BFS처럼 떠돌게 됩니다.
참고 2) n에서 가까운 a^b에서 b가 고정된 상태에서 n에서 가장 가깝게 하는 값을 a1, a2(a1 <= a2, a2 - a1 <= 1)라고 하면 a2^b - a1^b < 2000000000을 만족합니다. 이 값을 가장 크게 하는 999999999과 1000000000를 직접 대입해보면 됩니다.
도움이 됐으면 하네요 :)
dannydino 4년 전
무작정 찾는 코드로 작성하니 반례도 있을뿐더러 시간초과가 뜹니다.
10의 18승까지의 입력을 받아서 최솟값을 계산해야하는데 어떻게 계산시간을 줄일 수 있을까요?
아이디어좀 부탁드립니다..