2개의 댓글이 있습니다.
-
-
Being -
힌트: http://en.wikipedia.org/wiki/Addition_Chain, http://en.wikipedia.org/wiki/Addition-subtraction_chain 을 참고해 보세요. 최소의 연산 횟수를 찾는 문제는 NP-Complete 에 속합니다. 문제에 주어진 N의 범위가 1000 이하임에 주목해 보세요.
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
알찾기
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3621
얼마전에 가입하여 에디토리얼에 올라온 풀이들을 보면서
좀 더 일찍 가입할 껄 이라는 생각을 한참하는 뉴비입니닷...
대강 문제를 설명드리면,
x^n을 가장 빠르게 구하는 방법을 찾고 싶은 문제입니다.
예를 들어
x^31을 구하고 싶으면,
x*x= x^2, x^2*x^2=x^4, x^4*x^4=x^8, x^8*x^8=x^16,
x^16*x^16 = x^32, x^32/x = x^31
이렇게 최소 6번의 연산을 통하여 x^31을 구할 수 있다고 합니다.
곱하기와 나눗셈만 가능하고 x^-3과 같이 - 지수는 없다고 할 때 n을 주면 최소 연산횟수를 찾는 건데여...
어떻게 해야 할까요 ㅠㅠㅠ
13년 전