오일러프로젝트 016

오일러 프로젝트 016

2^1000의 모든 자리 숫자의 합

http://euler.synap.co.kr/prob_detail.php?id=16

2^15 = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.

2^1000의 각 자리수를 모두 더하면 얼마입니까?

풀이

2^1000은 큰 수를 지원하는 언어의 경우 간단히 풀이된다.

def p16():
    print(sum([int(x) for x in str(2**1000)]))

%time p16()
# 1366
# Wall time: 0 ns

큰 수를 지원할 수 없는 범위에서는 큰 수를 흉내내는 테크닉이 필요하다. 문자열을 숫자처럼 더하는 함수를 하나 작성한다. 이 함수는

1) 뒤에서부터 각 자리수와 올림값을 더해서
2) 10보다크면 올림값을 주고, 1의 자리만 취한다.
3) 모든 자리 및 남아있는 올림값을 다 처리한 후
4) 결과값을 역순으로 이어붙이면 된다.

A에 A를 한 번 더하면 2를 곱한 값이 되므로, 이 과정을 1000회 반복한다.

// Swift 2.0

import Foundation


func timeit(@noescape f:()->()) {
    let startTime = NSDate()
    f()
    let elapsed = NSDate().timeIntervalSinceDate(startTime)
    print("time: \(elapsed * 1000) ms")
}

func convert(s:String) -> [Int] {
    return Array(s.utf8).map{ Int($0) - 48 }
}


extension String {
    subscript(r:Range<Int>) -> String {
        let subRange = advance(startIndex, r.startIndex)..<advance(startIndex, r.endIndex)
        return self[subRange]
    }
}

func add(s1:String, _ s2:String) -> String {
    let n1 = convert(s1)
    let n2 = convert(s2)

    var resultList = [Int]()
    var flag:Int = 0

    let l = max(n1.count, n2.count)
    for i in 0..<l {
        let x = i < n1.count ? n1[i] : 0
        let y = i < n2.count ? n2[i] : 0
        var temp = x + y + flag
        if temp > 9 {
            flag = 1
            temp = temp - 10
        } else {
            flag = 0
        }
        resultList.append(temp)
    }

    if flag != 0 {
        resultList.append(flag)
    }

    return resultList.reverse().map{String($0)}.reduce("", combine:+)
}

timeit{
    var a = "2"

    for _ in 1..<1000 {
        a = add(a, a)    
    }

    let result = convert(a).reduce(0, combine:+)
    print(result)
}

//1366
//time: 584.853947162628 ms

오일러 프로젝트 13번 풀이에 사용된 BigInt 타입을 응용하면 좀 좀 더 빠른 결과를 볼 수 있다.