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