77번문제는 앞선 문제인 76번이나 31번과 완전 같은 문제라 할 수 있다. 다만 동전의 액면가가 N 보다 작은 소수들이면 된다.
오일러 프로젝트 77 더보기[태그:] 오일러프로젝트
오일러 프로젝트 73
오일러 프로젝트 73번 문제는 기약진분수에 대한 문제이다. 이전 두 문제에서 오일러 피함수와 관계한 기약 진분수의 문제는 악몽과 같은 수행 시간을 보였는데, 이 문제는 그나마 스케일이 조금 작아서 그다지 어렵지 않다.
오일러 프로젝트 73 더보기오일러 프로젝트 39
오일러 프로젝트 39 더보기세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.
{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
p가 1000이하일 때, 세변의 길이가 모두 자연수인 직각삼각형을 가장 많이 만들 수 있는 p의 값은 얼마입니까?
원문 : http://euler.synap.co.kr/prob_detail.php?id=39
오일러 프로젝트 38
오일러 프로젝트 38 번 문제는 반복된 곱셈의 결과를 이어 붙인 것이 1-9 팬디지털 숫자를 만들어 내는지를 보고, 그렇게 만들어지는 팬디지털 숫자중에 가장 큰 값을 찾는다. 문제 그대로를 코딩하면 되는 것이기도 하고 검사 범위도 매우 좁기 때문에 1도 어렵지 않은 문제이다.
숫자 192에 1, 2, 3을 각각 곱합니다.
92 × 1 = 192
192 × 2 = 384
192 × 3 = 576곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 ‘곱해서 이어붙이기’라고 부르기로 합니다. 같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다. 어떤 정수와 (1, 2, … , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1) (http://euler.synap.co.kr/prob_detail.php?id=38)
접근
어떤 수 N에 대해서 1부터 9사이의 값 i (1, 2, 3 .. 9) 와 곱한 결과들을 모아서 팬디지털이 되는지 검사한다. 즉 문제의 내용 그대로를 코딩하면 된다.
- 임의의 수 n에 대해서
- 1, 2, 3..을 차례로 곱해나가면서, 곱한 값을 연결한다.
- 2의 과정을 반복하다가 결과가 9자리 이상이 되면 1-9 팬디지털인지 검사한다.
참고로 범위는 어떻게 정할까? 6자리의 경우 1, 2를 곱해서 붙이면 기본 12자리가 되므로 실패. 따라서 5자리 범위까지만 테스트한 후 최대값을 찾으면 되겠다.
def test(n):
s = ""
for i in range(1, 10):
s += str(i * n)
if len(s) >= 9:
break
if "".join(sorted(s)) == "123456789":
return s
return None
def e038():
print(max(test(x) for x in range(1, 100_000) if test(x)))
%time e038()
Swift 풀이
동일한 알고리듬이다. 사실 펜디지털 숫자를 만들 수 있냐 없냐를 가지고 파이썬의 test
함수가 문자열 혹은 None
을 리턴했는데, 이는 옵셔널을 리턴하는 함수의 컨셉과 일치한다. 그리고 이렇게 이어진 결과에서 non-nil인 결과만을 추려내고 싶다면 flatMap
을 쓰는 것이 가장 간편하다.
// Swift 4.0
func test(_ n: Int) -> String {
var s = ""
for i in 1...9 {
s += "\(n * i)"
if s.count >= 9 { break }
}
// 문자열을 정렬하는 것은 유니코드 문자배열을 정렬한 것이므로 [Chracter] 타입이 된다.
// 따라서 이는 Characater의 시퀀스이므로 String으로 바로 만들 수 있다.
if String(s.sorted()) == "123456789" { return s }
return nil
}
print((1...99999).flatMap(test).max()!)
오일러 프로젝트 37
오일러 프로젝트 37 번 문제는 순환소수와 약간 비슷하지만, 의외로 성가신 구석이 매우 많은 문제이다. 동시에 잘 설계된 가드가 얼마나 수행 속도를 빠르게 만들어줄 수 있는지에 대한 좋은 예이기도 하다.
Update: 코드를 처음부터 새로 작성했다. 처음 이 풀이를 작성했을 때 처리 시간은 약 8초 가량이었는데, 1초대로 줄였다. 소수 검사 함수를 메모이제이션하는 등의 테크닉을 적용하면 수행 속도를 조금 더 올릴 수 있다.
소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다. 이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요. (참고: 2, 3, 5, 7은 제외합니다) (http://euler.synap.co.kr/prob_detail.php?id=37)
오일러 프로젝트 37 더보기