오일러 16번

2^1000 값의 자리수들을 모두 더한 값을 구하는 문제이다.

2^1000 을 display 할 수 없으므로 c 언어로는 풀기가 까다로운 면이 있다. 머리를 많이 굴려봤지만 별수가 떠오르지 않았다..한가지 떠오른 건 13번 문제처럼 숫자를 문자로 치환하면 큰 값들을 처리할 수 있고 풀 수 있지 않을까라고 생각했다.

정답을 찾아 제출하고 다른 사람들이 푼 방법들을 봤는데 문자열을 이용해 풀고 동적할당하는 방식이 가장 이상적으로 보여 아래와 같이 풀었다.

1. 이중 for문을 사용하는데 바깥 for문은 2를 1000번 곱하는 큰 과정이고 내부 for문은 각 자리수들을 처리하기 위한 for문이다, 내부 for문의 횟수는 문자열 배열의 크기만큼 반복을 하게 된다.

2. digit, temp[j], carry 라는 변수에 각각 *2 를 한 숫자, 10으로 나눈 나머지, 10으로 나눴을 때의 몫을 구해 대입한다.

2-1. 이 때 carry를 각 변수들에게 같이 더해준다, carry를 더하는 이유는 십의자리 이상인 값들의 경우 곱하기 2를 하고 나누었을 때 자리올림수가 발생하기 때문이다.

3. carry 값이 0 이 아닐 때 해당 값을 문자열에 대입해준다, 그리고 carry를 0으로 초기화해준다.

예를 들어

2부터 시작한다고 했을 때

temp의 i번째에 있는 값에 2 를 곱한 수를 digit에 대입하고( digit = 4 )

digit을 %10 하여 나온 값을 문자로 치환해 문자열 배열 temp에 대입한다 ( temp[0] = 4)

digit을 /10 하여 나온 값을 carry에 대입한다. (carry = 0)

....

temp의 i번째에 있는 값에 2 를 곱한 수를 digit 에 대입(16)

digit을 %10 하여 나온 값을 문자열 배열 temp에 대입한다( temp[0] = 6 )

digit을 /10 하여 나온 값을 carry에 대입한다. ( carry = 1)

이 때 carry는 0이 아니므로 이 값을 temp 문자열에 대입해준다. 이렇게 함으로써 문자열의 총 길이가 2로 늘어났다.

다음 횟수때부턴 두 번 반복하게 될 것이다, 문자열에는 temp[0] = 6, temp[1] = 1 과 같이 정렬되어 있다.

temp의 i번째에 있는 값에 2 를 곱한 수를 digit 에 대입(12)

digit을 %10 하여 나온 값을 문자열 배열 temp에 대입한다 ( temp[0] = 2)

digit을 /10 하여 나온 값을 carry에 대입한다. ( carry = 1 )

carry라는 자리올림수에 값이 생겼는데 이를 temp[i+1] 번째에 넘겨주어야 한다, 그러므로 carry를 추가로 더해주는 것이다, 이러한 과정을 반복해 1000번까지 하면 정답을 구할 수 있다.

해당 풀이는 메모리를 직접 관리하기에 더 정교하게 풀었다고도 볼수 있지만 C언어의 문제점은 메모리의 접근을 쉽게 허용하여 치명적인 문제를 야기할 수 있는 부분이므로, vector를 이용해서 자동으로 메모리를 관리할 수 있게 하여 푸는 방법이 조금 더 안전하지 않을까라는 생각을 하였다.

C언어로 풀었을 때는 memset, memcpy 를 사용하여 풀 수 있겠고 C++ 을 사용하면 string 과 vector 같은 자료구조를 이용해서도 풀면 좋을 것 같다.

비교해보니 string과 vector을 사용하지 않고 문자열의 크기를 직접지정해주며 동적할당해주는 C언어의 방식이 더 빠르다.

속도와 안정성, 어떤 방식을 선택할 지는 푸는 사람의 마음일 것 같다.