문제 35, 고고학자의 딜레마, The Archeologist's Dilemma, PC/UVa ID : 110503/701, 인기도 : A, 성공률 : 낮음, 레벨 : 1

문제 35, 고고학자의 딜레마, The Archeologist's Dilemma, PC/UVa ID : 110503/701, 인기도 : A, 성공률 : 낮음, 레벨 : 1

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• Mozila Firefox 4
  
• eclipse 3.6.1 + vrapper
  
• java
  

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 35, 고고학자의 딜레마, The Archeologist's Dillemma, p.155)
  

참조 링크

• http://uva.onlinejudge.org/external/7/701.html : 문제 원문
  

간략한 이야기/프로그램의 입출력

과거 지구에 외계 문명이 존재했다는 것을 밝혀줄 증거를 찾고 있는 고고학자가 이상한 숫자가 한 줄로 나열되어 있는, 부서진 벽을 발견했다. 이 숫자들의 왼쪽 부분은 상태가 아주 양호해서 숫자가 잘 보이지만 안타깝게도 오른쪽 부분에 있는 숫자들은 풍화로 인해 잘 안 보이는 것이 많다. 그 고고학자는 잘 보이는 숫자는 모두 2의 거듭제곱이라는 것을 발견하고는 모든 숫자들이 2의 거듭제곱이라는 가설을 세웠다.

그녀는 이 가설을 뒷받침하기 위해 잘 보이는 숫자의 개수가 잘 보이지 않는 숫자의 개수보다 적은 숫자들을 목록으로 정리했다. 그리고는 당신에게 목록에 있는 것과 같은 첫번째 자리의 숫자를 가지는 가장 작은 2의 거듭제곱을 찾아달라고 부탁했다.

어떤 정수가 주어졌을 때 2의 몇 제곱의 첫째 자리의 숫자(맨 왼쪽에 있는 숫자)가 그 정수와 같게 되는 가장 작은 지수 E를 결정하는 프로그램을 만들어야 된다.(숫자 가운데 절반 이상은 보이지 않는다.)

입력

• 각 행에는 2,147,483,648보다 크지 않은 양의 정수 N이 들어있다.

출력

• 각 정수에 대해 2의 몇 제곱의 첫째 자리 숫자가 주어진 숫자 N과 같게 되는 가장 작은 양의 정수 E를 출력한다.(한줄에 하나씩). 만약 그런 정수 E가 없다면 "no power of 2"라고 출력한다.
  

맛보기 사진

맛보기 코드 with JAVA

// ikpil.com // The Archeologist's Dilemma // PC/UVa ID : 110503/701 package problems_035_the_archeologists_dilemma; import java.util.*; class TheArcheologistDilemma { public static void main(String args[]) { Scanner kb = new Scanner(System.in); while (kb.hasNextInt()) { int n = kb.nextInt(); if (0 == n) break; int e = findMatchingSquareroot(n); if (0 != e) System.out.println(e); else System.out.println("no power of 2"); } } public static int findMatchingSquareroot(int in) { for (int g = 1; g < 9999 ; ++g) { int pn = positionalNumber(in) + g; double commonValue = pn * log2(10); double minValue = log2(in) + commonValue; double maxValue = log2(in + 1) + commonValue; int condidateE = (int)Math.ceil(minValue); if (condidateE < maxValue) return condidateE; } return 0; } public static int positionalNumber(int in) { int pn = 0; int temp_in = in; while (0 != temp_in) { temp_in /= 10; ++pn; } return pn; } public static double log2(int in) { return Math.log(in) / Math.log(2); } }

package problems_035_the_archeologists_dilemma; import static org.junit.Assert.*; import org.junit.Test; public class TheArcheologistDilemmaTest { @Test public void testFindMatchingSquareroot() { assertTrue(7 == TheArcheologistDilemma.findMatchingSquareroot(1)); assertTrue(8 == TheArcheologistDilemma.findMatchingSquareroot(2)); assertTrue(20 == TheArcheologistDilemma.findMatchingSquareroot(10)); assertTrue(9803 == TheArcheologistDilemma.findMatchingSquareroot(9932)); } @Test public void testPositionalNumber() { assertTrue(2 == TheArcheologistDilemma.positionalNumber(10)); assertTrue(4 == TheArcheologistDilemma.positionalNumber(9999)); assertTrue(8 == TheArcheologistDilemma.positionalNumber(99999999)); } }

여담

• pow로 문제를 풀 수 있으나, 너무 노가다성 작업이라, 답지를 봤었다. 답지는 상용 log 가지고 풀었다.
  그래서 나도 다시 풀기 위해 "공통수학, log"를 다시 봤다. 하지만 사용로그 성질 이해 부분에서 탁 막혔다. : )
  

:wq!