반응형
프로젝트 오일러.md

프로젝트 오일러 23번 문제

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?


파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# -*- coding: utf-8 -*-
import math
 
#진약수를 모두 더한 값을 반환하는 함수
def divisors_sum(num):
    result = 0
    temp = math.sqrt(num)
       
    #n의 약수를 구할 때, 1부터 루트 n까지만 나눠본다. 나눠서 약수이면, n에서 해당 약수를 나눈 수도 약수이다.
    for i in range(1,int(temp)+1):
        if (num % i == 0):
            result += i + num/i
            if(temp == int(temp) and i == temp): #루트num 중복제거
                result -= i
    
    result -= num #자기자신을 뺀다
    return result
    
 
#num이 초과수이면 true, 아니면 false를 반환하는 함수
def Is_abundant_number(num):
    if(num < divisors_sum(num)): #num의 진약수의 합이 num보다 크면 초과수
        return True                                                                                       
    else:
        return False
        
abundant_list = [] #초과수를 저장할 리스트
sum_abundant_set = set() #2개의 초과수 합을 저장하는 집합
 
for n in range(12,28123):
    if(Is_abundant_number(n) == True): #n이 초과수이면 초과수 리스트(abundant_list)에 저장
            abundant_list.append(n)
    
 
#2개의 모든 초과수 합을 구함
for i in abundant_list:
    for j in abundant_list:
        if(i+j < 28123):
            sum_abundant_set.add(i+j)
        
 
result = sum(range(1,28123)) - sum(sum_abundant_set)
print result
cs

풀이


초과수 리스트를 만든다. 초과수 리스트를 이용하여 2개의 초과 수 합 집합을 만든다. 집합을 사용한 이유는 자동으로 중복제거를 하기 위해서이다. 마지막으로 1부터 28123까지 합에서 2개의 초과 수 합을 빼면 답을 구할 수 있다. 

반응형
저작자표시

'programming' 카테고리의 다른 글

뇌를 자극하는 C# 5.0 프로그래밍 Chapter8 연습문제 풀이  (0) 2016.01.08
뇌를 자극하는 C# 5.0 프로그래밍 Chapter7 연습문제 풀이  (0) 2016.01.07
뇌를 자극하는 C# 5.0 프로그래밍 Chapter6 연습문제 풀이  (0) 2016.01.04
프로젝트 오일러(Project Euler) 22번 문제  (0) 2016.01.04
뇌를 자극하는 C# 5.0 프로그래밍 Chapter5 연습문제 풀이  (0) 2016.01.04
반응형
Untitled Document.md

프로젝트 오일러 22번 문제

여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요). 이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.

  • 먼저 모든 이름을 알파벳 순으로 정렬합니다.
  • 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, …, Z=26)를 모두 더합니다.
  • 여기에 이 이름의 순번을 곱합니다.

예를 들어 "COLIN"의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.

names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?




파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# -*- coding: utf-8 -*-
f = open("E:/names.txt",'r')
s = f.read()
f.close()
 
temp = s.split(',')
wordslist = [] #순수단어만 뽑아서 저장할 list
 
for words in temp: #단어 양옆에 "제거
    wordslist.append(words.strip('"'))
 
wordslist.sort() #단어를 알파벳 순으로 정렬
 
#알파벳에 해당하는 숫자(점수)
point = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
result = 0 #단어의 점수를 총합할 변수
words_point = 0 #각 단어의 점수를 저장할 변수
index = 1 #몇번째 단어인지 위치를 나타내는 변수
 
for words in wordslist:
    for alphabet in words:
        words_point += point[alphabet]
    result = result + words_point * (wordslist.index(words)+1) #한 단어의 점수 합과 해당 단어의 위치를 곱한다
    words_point = 0
 
print result
cs




코드설명

파일을 읽어온다. 텍스트 파일에서 ,를 기준으로 단어를 나누어 리스트(temp)에 저장한다. 그 후, 단어양옆에 "을 제거하여 순수한 알파벳 단어만 남게하여 리스트(wordslist)에 저장한다.


리스트 내장함수 sort를 이용하여, 단어를 알파벳 순으로 정렬한다. 알파벳별 점수를 나타내는 point라는 사전을 만든다. 그 후, 리스트에서 단어를 하나씩 꺼내서 각 알파벳별 점수를 더한다. 그리고 정렬된 단어 순서를 곱하여 최종적인 점수를 구한다.


반응형
저작자표시

'programming' 카테고리의 다른 글

프로젝트 오일러(Project Euler) 23번 문제  (0) 2016.01.07
뇌를 자극하는 C# 5.0 프로그래밍 Chapter6 연습문제 풀이  (0) 2016.01.04
뇌를 자극하는 C# 5.0 프로그래밍 Chapter5 연습문제 풀이  (0) 2016.01.04
뇌를 자극하는 C# 5.0 프로그래밍 Chapter4 연습문제 풀이  (0) 2015.12.30
[안드로이드]안드로이드 4대 컴포넌트  (3) 2015.11.06

+ Recent posts

티스토리툴바