문제 36, 1의 개수, Ones, PC/UVa ID : 110504/10127, 인기도 : A, 성공률 : 높음, 레벨 : 2

문제 36, 1의 개수, Ones, PC/UVa ID : 110504/10127, 인기도 : A, 성공률 : 높음, 레벨 : 2

이 포스트를 만든 목적

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

이 포스트의 준비물

• Mozila Firefox 4
  
• eclipse 3.6.1 + vrapper
  
• java
  

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 36, 1의 개수, Ones, p.156)
  

참조 링크

• http://uva.onlinejudge.org/external/101/10127.html : 문제 원문
  

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

2나 5로 나눌 수 없는 0 이상 10,000 이하의 정수 n이 주어졌는데, n의 배수 중에는 10진수로 표기 했을 때 모든 자리 숫자가 1인 것이 있다. 그러한 n의 배수 중에서 가장 작은 것은 몇 자리 수일까?

입력

• 한 줄에 하나씩의 정수가 들어있는 파일
  

출력

• 한줄에 하나씩 출력 하며, n의 배수이면서, 제일 적은 자릿수를 출력할 것
  

맛보기 사진

맛보기 코드 With JAVA

// http://ikpil.com // 1의 개수, Ones // PC/UVa ID : 110504/10127 package problem_036_ones; import java.util.Scanner; public class Ones { public static void main(String args[]) { Scanner kb = new Scanner(System.in); while (kb.hasNextInt()) { int n = kb.nextInt(); if (0 == n) break; if (0 == (n % 2) || 0 == (n % 5)) break; long pN= findSmallestPositionalNumber2(n); System.out.println(pN); } } // version 1 public static long findSmallestPositionalNumber(int n) { long cN = 0, pN = 0; do { cN += Math.pow(10, pN++); } while (0 != (cN % n)); return pN; } // version 2 public static long findSmallestPositionalNumber2(int n) { long pN = 0, modSumN = 0; do { long modN = (modSumN * 10) + 1; modSumN = (modN % n); ++pN; } while (0 != modSumN); return pN; } }

package problem_036_ones; import static org.junit.Assert.*; import org.junit.Test; public class OnesTest { @Test public void testFindSmallestPositionalNumber() { assertTrue(3 == Ones.findSmallestPositionalNumber(3)); assertTrue(6 == Ones.findSmallestPositionalNumber(7)); assertTrue(12 == Ones.findSmallestPositionalNumber(9901)); } @Test public void testFindSmallestPositionalNumber2() { assertTrue(3 == Ones.findSmallestPositionalNumber2(3)); assertTrue(6 == Ones.findSmallestPositionalNumber2(7)); assertTrue(12 == Ones.findSmallestPositionalNumber2(9901)); } }

여담

• 1의 개수를 찾는 버전1/버전2 가 있는데, 버전1은 처음에 만든 것이고, 버전2는 그 후에 만든 것이다. 이렇게 두개의 버전이 있는 이유는, 버전1에서 후보변수가 64bit를 초과 했을 때, 대책이 없기 때문이다. 버전2는 자릿수가 64bit 를 초과할 때까지 여유가 있다.

:wq