Project Euler Problem16

Power digit sum

Problem 16

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

나의 풀이)

2의 1000승을 표현하기는 매우 어렵다.

기본적으로 몇 백자리의 수가 나오기때문에.. 표현할 수 있는 자료형이 없다.

게임 아카데미 동기가 라지넘버 라이브러리를 쓰면 된다는데..

찾아보니 gmp인거 같은데.. 설치가 귀찮아 이 방법은 접는것으로...

처음 배열로 구현하려고 str[500]만큼의 배열로 선언하여 계산했다.

고정된 배열 길이로 구하려니.. 뒤에 자리들 처리해주는게 여간 성가신게 아니었다.

그래서 벡터나 리스트 중에 뭐 써볼까 하다가 리스트로 작성해보았다.

사실 백터가 이번 문제에 더 어울렸지만.. 

1. 각 자리 수 * 2

2.1 10이 넘어가는 자리 수 %10(나머지 저장), 다음 자리 +1

2.2 다음 자리가 없다면 노드 1로 추가

3. sum(list) 출력

사실 대부분의 사람들이 비슷한 형태로 풀었다. 알고리즘은 대부분 거기서 거기.

역시 배열로 충분히 구현할 수 있는걸 리스트로 구현했더니 속도가 조금 문제가 있었다.

이더레이터에 노드 추가 연산 등등 오버헤드로 인한 속도저하가..

그 외에는 스트링에 때려박아서 한 개씩 잘라 계산하는 방법도 있었다.

2의 10000만 승을 출력해보았다.