Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
...............
[출처 - projecteuler.net/]
이번에는 50개의 자리수를 가지는 숫자들이 입력될 때, 그 합을 구해서 가장 왼쪽부터 10개의 자리수의 숫자를 출력하는 문제입니다.
해당 문제에 따르면 50개의 자리수 이기 때문에, 우리가 흔히 생각하는 Integer, Double등으로는 그 값을 다룰수가 없습니다. 왜냐하면 자리수가 너무 크기 때문입니다. 그렇다면... 어떤 방법이 있을까요?? 보통 입력을 받게되면 그 입력의 줄 단위당 string으로 받게됩니다.
그렇다면, string에 착안해서 뒤의 자리부터 시작해서 string을 추출하고 그 값들의 더하기를 수행하는 연산자를 새로 만들어 보는 것은 어떨까요?? 그리고 그 결과는 다시 string으로 저장을 하는 것이죠... 그러면 최종적으로 결과를 출력할때 string의 '+' 로 구현하면 오히려 더 간단하게 구현이 가능할 테니까요...
그럼 한번 구현을 해보겠습니다.
1. Basic
왠지 이 문제는 그냥 단순히 구현을 하면 되는 문제로 보입니다. no12를 구하기 위해서는 뭔가 알고리즘이 최적화하여 들어가야 하겠지만... 응답을 위해서 기다리는 시간이 너무 길어지기 때문에, 아마 조건보다 약간만 가혹한 환경이 주어지게 되면 아무래도 그 결과는 나오지 않을 것 입니다.
[소스코드]
import time
if __name__ == '__main__':
line = int(input())
mat = []
for i in range(line):
temp = [a for a in input().strip()]
mat.append(temp)
start = time.time()
res = []
remains = 0
for i in range(50):
sum = 0
for j in range(line):
sum += int(mat[j][50-i-1])
sum += remains
remains = sum // 10
res.append(str(sum % 10))
if remains != 0:
res.append(str(remains))
answer = ''
for i in range(len(res)):
answer += res[len(res)-i-1]
if len(answer) == 10:
break;
print('정 답 : ', answer)
end = time.time()
print('소요시간 : ', end - start)
은근 코드는 간단해 보이지 않나요?? 아무래도 입력에 대해서 각 자리수 별로 더하기를 구하고 그 몫은 나머지에 저장하고, 나머지는 결과 list에 적재하는 방법으로 구현하는 그나마 단순한 문제이기 때문입니다.
여기서 한가지 생각해 볼 만한 내용이 있습니다. 총 100개의 입력되는 50자리 수를 보면, 어떤 경우에는 가장 앞자리의 수의 합이 한자리가 나올 수도 있고... 아니면 최대 3자리가 나올 수도 있습니다.
ex) 50자리의 입력값들의 구성이... 0989890.....250 이렇게 제일 앞자리가 0인 것들로 구성된다면 최종합의 가장 앞자리는 0일 것입니다. 하지만 98799887637.....432 이렇게 제일 앞자리가 9인 것드로 구성이 된다면... 최종합의 가장 앞자리는 999가 될 것입니다.
따라서, answer[ ] 의 가장 마지막 항목에는 '999' 가 들어가겠죠?? 따라서 결과를 출력하는 부분에서는 현재 내가 자리수가 몇인가를 체크를 해주어야 합니다. 똑똑하게 가장 마지막 수의 길이를 len으로 체크하고 나머지 수만큼 붙여줘도 되겠으나... 최대 10개의 for만 수행하면 되기 때문에 그냥 체크를 하도록 했습니다.
[주의 Point]
if remains != 0:
res.append(str(remains))
answer = ''
for i in range(len(res)):
answer += res[len(res)-i-1]
if len(answer) == 10:
break;자 그렇다면 그 결과는 어떻게 되었을까요??
[결과]
정 답 : 5537376230
소요시간 : 0.003999948501586914소요시간은 매주 적네요... 그렇다면 Advance까지 생각해 볼 필요는 없어보입니다!!!
- Ayotera Lab -
댓글