(프로젝트 오일러 문제 16번) 2^15 = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다. 2^1000의 각 자리수를 모두 더하면 얼마입니까?
72개의 풀이가 있습니다.
print(eval('+'.join(str(2**1000)))) # 1366
1 << 1000 이렇게 비트연산을 안 해도 내부적으로 구현이 잘 되어있는지 거의 시간차 없이 바로 나옵니다.
하지만 문제 의도는 아마
def twosqr(n):
arr = [0] * (int(n/10*3)+2) + [1]
for i in range(n):
carrys = [x*2 // 10 for x in arr][1:] + [0]
remains = [x*2 % 10 for x in arr]
arr = [sum(x) for x in zip(carrys, remains)]
return arr
#print(''.join(map(str, twosqr(1000)))) # 2^n
print(sum(twosqr(1000)))
이렇게 직접 계산하라는 거겠지요. 2^10을 10진수 3자리로 얼추 계산해서 배열을 준비하고 2를 1000번 곱했습니다.
.
아니면 한자리씩 계산하지 말고... 32bit unsigned int라고 가정하고 대충 9자리씩 끊어서 요렇게.
이번에는 배열을 처음부터 안 만들고 10억 넘을 때마다 앞에 하나씩 붙여줬습니다.
def twosqr(n):
LIMIT = 1000000000
arr = [1]
for i in range(n):
if arr[0]*2 >= LIMIT:
arr = [0] + arr
for j in range(len(arr)):
carry, arr[j] = divmod(arr[j]*2, LIMIT)
arr[j-1] += carry
return ''.join(map(str, arr))
print(eval('+'.join(twosqr(1000))))
return ''.join(map(str, arr)) <-- 여기서 정확히 2^1000 은 안 나옵니다.
숫자로 끊어서 저장했기 때문에... 예를 들어서 "[1, 1]" 이런 숫자가 저장되어 있으면 "1" + "000000001" 이 아니라 "1" + "1"을 리턴합니다.
다만 0은 마지막 덧셈에 영향이 없기 때문에 결과는 틀리지 않습니다.
public class 이의천제곱의각자릿수의합은 {
public static void main(String[] args) {
BigInteger b1 = new BigInteger("2");
BigInteger b2 = b1.pow(1000);
BigInteger b3 = BigInteger.TEN;
BigInteger a= BigInteger.ZERO;
for(int i=0;;i++) {
if(b2.compareTo(b3)==-1) { //b2의 값이 10보다 작을경우
a=a.add(b2);
break;
}
else {
a=a.add(b2.mod(b3));
b2=b2.divide(b3);
}
}
System.out.println(a);
}
}
int GetWeekDay(int y, int m, int d);
int main()
{
int count = 0;
for( int y = 1901 ; y <= 2000 ; y++ )
{
for( int m = 1 ; m <= 12 ; m++ )
{
if( GetWeekDay(y, m, 1) == 0 ) count++;
}
}
printf("Ans = %d\n", count);
}
int GetWeekDay(int y, int m, int d)
{
if( m <= 2 ) { m += 9; y += 4799; } else { m -= 3; y += 4800; }
int days = 365*y + y/4 - y/100 + y/400 + (153*m+2)/5 + d - 32045;
return (days+1)%7;
}
a=str(2**1000)
b=[]
ans=0
for i in range(0,len(a)):
b.append(int(a[i]))
for i in b:
ans+=i
print(ans)
#1366
package practiceBasic.binaryOut;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class projectOiler16 {
public static void main(String[] args) {
System.out.println("BigInteger Calculation: " + bigIntegerCalculation(1000));
System.out.println("ArrayList Calculation: " + arrayListCalculation(1000));
}
private static int bigIntegerCalculation(int power) {
// 단순무식
BigInteger times = new BigInteger("2");
int temp = 0;
times = times.pow(power);
while (times.compareTo(BigInteger.TEN) >= 0) {
temp += times.mod(BigInteger.TEN).intValue();
times = times.divide(BigInteger.TEN);
}
temp += times.mod(BigInteger.TEN).intValue();
return temp;
}
private static int arrayListCalculation(int power) {
// ArrayList, doublyLinked가 더 좋을듯...
List<Integer> numList = new ArrayList<Integer>();
int temp = 0;
numList.add(1);
for (int i = 1; i <= power; i++) {
int ten = 0;
for (int n = 0; n < numList.size(); n++) {
int tmpNum = numList.get(n) * 2 + ten;
ten = tmpNum / 10;
numList.set(n, tmpNum % 10);
}
if (ten > 0)
numList.add(ten);
}
Iterator<Integer> itr = numList.iterator();
while (itr.hasNext())
temp += itr.next();
return temp;
}
}
python3로 작성했습니다.
print( sum( [ int(i) for i in str(2**1000) ] ) )
#실행결과
1366
사족으로, 2^1000은 다음과 같습니다.
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
파이썬으로 하면 2^1000 이나 100! 같은 엄청 큰 수에 대해서도 큰 어려움 없이 계산이 가능합니다.
print(sum(int(x) for x in str(2**1000)))
Swift와 같이 정수타입 크기에 제한이 있고, 큰 정수를 지원하지 않는 경우에는 좀 다른 접근이 필요합니다. 10진수 1234는 10이라는 상수를 항으로하는 4차 다항식으로 볼 수 있습니다. (1 * 10^3 + 2 * 10^2 + 3*10^1 + 4 * 10^0) 이 때 두 10진수를 더했을 때 각 항의 계수가 9를 넘어서면 그 차이만큼 상위 항이 하나 더 추가되어 합산됩니다. 곱셈의 경우에도 두 다항식을 곱하는 식으로 정리하고, 계수가 10이상인 항을 상위항으로 올려주는 처리를 해서 정리하게 됩니다.
이 룰을 따라서 큰 수의 덧셈이나 곱셈을 처리할 수 있는 타입을 만들 수 있습니다. 여기서는 10,000을 단위로 하는 다항식으로 큰 수를 다루는 타입을 작성해보도록 하겠습니다. 덧셈이랑 곱셈만 지원하고 부호는 딱히 생각하지 않습니다. 먼저 각 항의 단위가 되는 노드를 다음과 같이 정의합니다.
struct Node {
static let limit = 10_000
let value: Int
let unit: Int
init(value:Int, unit: Int=0) {
self.value = value
self.unit = unit
}
func mutiplying(_ other: Node) -> [Node] {
let unit = self.unit + other.unit
var value = self.value * other.value
if value < Node.limit { return [Node(value:value, unit:unit)] }
let upFlag = value / Node.limit
value = value % Node.limit
return [Node(value: upFlag, unit: unit+1), Node(value:value, unit: unit)]
}
}
이번에는 이 항들을 모아서 큰 정수를 표현하는 타입을 정의해봅니다.
struct BigNumber {
var data: [Node]
// 정수로부터 초기화
init(integer n: Int) {
var n = n
var temp: [Node] = []
var unit = 0
while n > 0 {
temp.append(Node(value: n % Node.limit, unit: unit))
n = n / Node.limit
unit += 1
}
self.data = temp
}
// 노드리스트로부터 초기화
init(nodes:[Node]) {
var temp: [Node] = []
let maxUnit = nodes.map{ $0.unit }.max() ?? 0
var upFlag = 0
for unit in (0...maxUnit) {
var value = nodes.filter{ $0.unit == unit }.map{ $0.value }.reduce(0, +) + upFlag
if value >= Node.limit {
upFlag = value / Node.limit
value = value % Node.limit
} else {
upFlag = 0
}
temp.append(Node(value: value, unint: unit))
}
if upFlag > 0 {
temp.append(Node(value: upFlag, unit: maxUnit + 1))
}
}
문자열로부터 초기화하는 이니셜라이저도 필요하겠지만, 일단 이 문제에서는 필요없으니 제외하겠습니다. 다음은 덧셈과 곱셈을 적용할 수 있게 합니다. 덧셈은 두 다항식의 모든 항을 정리하면 됩니다. 곱셈은 두 다항식의 각 항을 곱하고 그 결과를 정리합니다.
extension BigNumer {
static func + (left: BigNumber, right: BigNumber) -> BigNumer {
return BigNumer(nodes: left.data + right.data)
}
static func * (left: BigNumer, right: BigNumber) -> BigNumer {
let nodes = left.data.flatMap{ n in right.data.flatMap{ $0.multiplying(n) }}
return BigNumer(nodes: nodes)
}
}
이제 계산은 할 수 있으니, 결과를 출력해야겠네요. 각 노드를 unit 역순으로 정렬하고, 노드 값을 4자리 문자열에 포맷팅합니다. String(format:_,_) 을 써도 되는데, 기왕에 Foundation을 반입 안했으니, 그냥 무식하게 "0"으로 패딩 주고 자르는 방식을 선택합니다. 끝으로 첫 항이 4자리 미만인 경우에 앞에 00이 붙는 경우가 있을 수 있으니 이건 떼도록 하겠습니다.
extension BigNumer: CustomStringConvertible {
var description: String {
let numbers = nodes.sorted{ $0.unit > $1.unit }.map{ n in
let s = "0000" + "\($0.value)"
let pos = s.index(s.endIndex, offsetBy: -4)
return s[pos...]
}.joined(separator:"")
if let nz = numbers.index(where: { $0 != "0" }) {
return numbers[nz...]
}
return numbers
}
}
이제 2^1000을 계산하면 되겠네요.
func pow(_ base: BigNumber, _ e: Int) -> BigNumber {
guard e > 0 else { return BigNumber(integer: 0) }
let r = pow(base, e/2)
if e % 2 == 0 { return r * r }
return r * r * base
}
마무리입니다.
let a = BigNumer(integer: 2)
print(pow(a, 1000).description.characters.flatMap{ Int(String($0)) }.reduce(0, +))
clojure
(print(apply +(map #(-(int%)48)(str(apply *'(repeat 1024 2))))))
좀 더 줄일 수 있을 텐데 말이죠...
#(-(int%)48)는 각 글자 코드 값에서 '0' 코드 값 48을 빼는 코드에요
// golang 1.9
package main
import (
"fmt"
"math"
"strconv"
)
func main() {
// sum digits function
sum := func(s string) int {
lsum := 0
for i := 0; i < len(s); i++ {
nsn, _ := strconv.Atoi(string(s[i]))
lsum += nsn
}
return lsum
}
//
fmt.Println(sum(fmt.Sprintf("%.f", math.Exp2(1000))))
}
// ans: 1366
이번에는 C#으로 풀어 봤습니다. 난이도가 낮아서 그런지 C++과 크게 차이는 없네요
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleforTest
{
class Program
{
static void Main(string[] args)
{
int num;
int num2 = 1; //2의 n승을 저장할 변수
int DivideNum = 1; //1부터 10 씩곱해서 나눠줄 변수
int answer = 0; //답을 입력
num = int.Parse(Console.ReadLine());
Console.WriteLine(num);
num2 = (int)Math.Pow(2, num); //라이브러리
//그냥 계산했을때..
/*for(int i = 0; i < num; i++)
{
num2 *= 2;
}*/
Console.WriteLine("2의 n승은 : " + num2);
while(true) //1의 자리부터 ~ 맨윗자리 까지
{
if (num2 / DivideNum > 1) //10단위로 나누어서 1보다 크면 그수로 나눠주면 된다는 얘기
{
int temp = (num2 % (DivideNum * 10)); //구하는 단위의 윗자리를 제거
answer += (temp / DivideNum); //해당 자리를 1단위로
DivideNum *= 10; //나누는 자릿수 증가
}
else
break; //모두 계산했을때
}
Console.WriteLine(answer);
}
}
}
function power(pow){
var befNum = [1];
var aftNum = new Array();
var temNum;
var odFlag = false;
for(var i=1;i<=pow;i++){
aftNum = [];
for(var j=befNum.length-1;j>=0;j--){
temNum = befNum[j];
temNum = temNum * 2;
if(odFlag == true){
temNum += 1;
odFlag = false;
}
if(temNum < 10){
aftNum.unshift(temNum);
odFlag = false;
}else{
aftNum.unshift(temNum - 10);
if(j == 0) aftNum.unshift(1);
else odFlag = true;
}
}
befNum = aftNum;
}
temNum = 0;
for(var k=0;k<befNum.length;k++){
temNum += Number(befNum[k]);
}
console.log(i-1 + " : " + temNum);
}
power(1000);
결과가 나오긴 하는데 성능은 똥이네요.. ㅋㅋ 손좀 봐야겠어요
const calc = (arr, index, value) => {
arr[index] = value % 10;
value = Math.floor(value / 10);
if (value) {
if (!arr[++index]) {
arr.push(0);
}
calc(arr, index, arr[index] + value);
}
};
const exponentiation = (base, exp) => {
const result = [1];
for (let i = 1; i <= exp; i++) {
let length = result.length;
for (let j = length - 1; j >= 0; j--) {
calc(result, j, result[j] * base);
}
}
return result.reduce((s, v) => s += v, 0);
};
console.log(exponentiation(2, 1000));
저는 계산된 수를 string으로 만들어 리스트에 쪼개어 인자로 집어넣었습니다.
그 후 해당 인자들을 모두 integer로 변환시킨 다음,
for문을 사용하여 합을 구했습니다.
a = 2**1000
position_numberlist = list(str(a))
converted_numberlist = [int(i) for i in position_numberlist]
result = 0
for i in converted_numberlist:
if i == 0:
continue
else:
result += i
print(result)
class i:
def __init__(self):
self.li = [1]
def double(self):
li = self.li
for i in range(len(li)):
li[i] *= 2
for i in range(len(li)):
if li[i]//10 == 1:
li[i] %= 10
try:
li[i+1] += 1
except IndexError:
li.append(1)
def __str__(self):
return ''.join(str(x) for x in self.li)[::-1]
if __name__ == '__main__':
n = i()
for x in range(1000):
n.double()
print(sum(int(x) for x in str(n)))
파이썬 3.6.2 64
Java 입니다.
import java.util.Scanner;
public class level_2_to_1000_squared {
public static void main(String[] args) {
System.out.println("2의 n제곱일때 n의 값을 입력하세요.");
Scanner sc = new Scanner(System.in);
int number = sc.nextInt();
sc.close();
int two = 2;
for(int i = 1; i < number; i++) // 제곱 계산.
{
two = two * 2;
}
int length = (int)(Math.log10(two)+1); // 제곱한 수 자릿수 계산.
int[] array = new int[length];
int temp = two;
int sum = 0; // 각 자릿수를 모두 더해 저장할 변수.
for(int i = 0; i < length; i++) // 각 자리수를 배열에 집어 넣는거기 때문에 앞, 뒤 순서 상관 없음.
{
array[i] = temp % 10;
temp = temp / 10;
}
for(int i = 0; i < length; i++)
{
sum = sum + array[i];
}
System.out.println("2의 " + number + "제곱의 각 자릿수 합 : " + sum);
}
}
each_num = list(str(2**1000)) # string 값을 list로 변환하면 각 자리의 숫자를 요소로 갖는 list가 형성됩니다.
total_sum = 0
for i in each_num:
each_int = int(i) # 각 자릿값이 string이기 때문에 int로 형변환을 해줍니다.
total_sum += each_int # 각 자릿값의 누적합을 구합니다.
print(total_sum)
def sumdigit(n):
if len(str(n)) == 1:
return n
else:
return sumdigit(int(str(n)[1:])) + int(str(n)[0])
print(sumdigit(2**1000))
n=2^1000
digit :: Integer -> [Integer]
digit 0 = []
digit x = digit(x `div` 10) ++ [x `mod` 10]
showdigit = show$sum$digit n
main = do
putStr$showdigit
def curculate(n , m):
return eval('+'.join(str(eval('*'.join(['2' for x in range(m)])))))
print(curculate(2, 1000))
static long f(long num) {
long sum = 0;
while (num > 0) {
sum += num %10;
num /= 10;
}
return sum;
}
public static void main(String[] args) throws Exception {
System.out.println(f((long)Math.pow(2, 1000)));
}
// 자바입니다
package test;
import java.math.BigInteger;
public class test {
public static void main(String[] args) {
BigInteger num = new BigInteger("2").pow(1000);
int sum = 0;
while (num.compareTo(BigInteger.ZERO) != 0) {
sum += num.mod(BigInteger.valueOf(10)).intValue();
num = num.divide(BigInteger.valueOf(10));
}
System.out.println(sum);
}
}
package studypac;
//import java.util.Scanner;
import java.math.*;
public class timestudy {
public static void main(String args[])
{
BigInteger verybignumber = new BigInteger("2").pow(1000);
String cheese = verybignumber.toString();
int converter=0,result = 0;
for(int i = 0; i <=cheese.length()-1;i++)
{
char c = cheese.charAt(i);
converter = (int)c;
result += converter - '0';
}
System.out.println("Answer is : " + result);
}
}
자바입니다.ㅠㅠ 출력-> Answer is : 1366
#2^n의 각 자릿수의 합
n=int(input("지수 입력: "))
num=2**n
sn=str(num)#문자열로 변환
sn.split()#문자열 분리
s=0
for i in range(len(sn)):
s0=int(sn[i])
s+=s0
print('각 자릿수의 합: ',s)
num = int(input("제곱 승 : "))
value = str(2**num)
sum = 0
for i in range(len(value)):
sum += int(value[i])
print(sum)
number = int(input())
calculate = list(str(number**1000))
summ = []
print(summ)
for i in range(0,len(calculate)):
summ.append(int(calculate[i]))
print(sum(summ))
print(sum([int(c) for c in str(2**1000)]))
-----------------------try------------------------------------------------ 혹시 문제점을 알려주실 수 있을까요 시도해봤는데 답이 다르게 나오네요. import math as m
def sumof_one_number(number,pows):
a=pows*(m.log(number,10))
numbers=m.modf(a)
for_answer=str(round(pow(10,numbers[0])*pow(10,numbers[1])))
answer=0
for i in for_answer:
answer+=int(i)
return answer
print(sumof_one_number(2,1000))
아마 이런식의 풀이를 원하시는게 아닐까 생각해봅니다..
a=[1]
for i in range(0, 1000):
if a[0]>4: a=[0]+a
for j in range(len(a)-1, -1, -1):
tmp=a[j]*2
a[j] = tmp%10
a[j-1]+=tmp//10/2
print(int(sum(a)))
def func(num1, num2):
temp_0 = 1
for i in range(num2):
temp_0 = num1 * temp_0
temp_1 = str(temp_0)
result = 0
for member in temp_1:
result += int(member)
return result
if __name__ == '__main__':
print(str(func(2,1000)))
def squared():
b = 0
for i in str(2**1000):
b += int(i)
return b
if __name__ == '__main__':
print(squared())
a = 2**1000
b = list(map(int,list(str(a))))
print(sum(b))
연산결과 -> 문자열 변환 -> 배열화하여 각 문자 원소화 -> Map 이용 각 원소 정수화 -> 정수화된 배열의 sum 값 출력
의도한바가 맞는지는 몰겠네요..
// Rust
// 큰 수를 다루기 위해 vector에 각 자리수를 넣고 그냥 단순 계산^^
fn power_n(n: u32) -> u32 {
let mut vec = vec![6, 1]; // 2^4
for i in 5..=n {
for v in &mut vec {
*v *= 2;
}
//tidy vector : 각 원소가 0~9를 갖도록 (10 이상이면 다음 칸으로 더해줌)
let l = vec.len();
for j in 0..l-1 {
if vec[j] >= 10 { vec[j+1] += vec[j] / 10;
vec[j] %= 10;}
}
if vec[l-1] >= 10 { vec.push(vec[l-1] / 10);
vec[l-1] %= 10;}
}
vec.iter().sum::<u32>()
}
fn t() {
assert_eq!(power_n(15), 26);
assert_eq!(power_n(1000), 1366);
}