접근 ¶
처음 문제를 이해하는데 대략 4분. '10진수' 라는 말에 현혹되었다가 샘플 데이터 보면서 간단히 감을 잡음.
처음에는 brute-force 틱한 방법 적용. 그러다가 세번째 샘플 데이터에서 엄청나게 속도가 저하되는 것을 느낌. 여태껏의 경험에 의하면 '무언가 다른 계산 방법이 있겠군' 이라는 감이 오다. brute-force 방법에서 미리 cut 을 할 방법을 이리저리 시도. (첫째자리와 끝자리만 1 비교.) 시간이 줄어들긴 하나 9901 예제에 대해서 금방 답이 나오진 않음. 9901 보다 큰 예제도 있을것이라 할때, 분명 금방 끝낼 방법이 있을 것이라는 확신은 드나, 생각이 떠오르지 않음.
어떻게 접근할까 하다가 지금까지 연습장을 안 쓰고 있음을 확인. 연습장을 꺼내는 순간 '팍' 하고 느낌이 오다.~ 그리고 바로 최종 코드 완료.
- 연습장에 적힌 숫자 : 1, 11, 111, 1111
최종 코드 ¶
~cpp import unittest def isAllOne(aValue): valueStr = str(aValue) for each in valueStr: if each != '1': return False return True def isMultiplyOf(aValue, mulValue): return aValue % mulValue == 0 def ones(aValue): theOnes = "1" while True: onesValue = int(theOnes) if isMultiplyOf(onesValue,aValue): return len(theOnes) theOnes += "1" class OnesTest(unittest.TestCase): def testSmall(self): self.assertEquals(3, ones(3)) self.assertEquals(6, ones(7)) def testSmall2(self): self.assertEquals(9, ones(9)) def testLarge(self): self.assertEquals(12, ones(9901)) def testIsAllOne(self): self.assert_(isAllOne(1111)) self.assert_(not isAllOne(1112)) def main(): print ones(int(raw_input())) if __name__=="__main__": #unittest.main(argv=('','-v')) main()