오일러 프로젝트 73

오일러 프로젝트 73번 문제는 기약진분수에 대한 문제이다. 이전 두 문제에서 오일러 피함수와 관계한 기약 진분수의 문제는 악몽과 같은 수행 시간을 보였는데, 이 문제는 그나마 스케일이 조금 작아서 그다지 어렵지 않다.

오일러 프로젝트 73 더보기

오일러 프로젝트 39

원문 : http://euler.synap.co.kr/prob_detail.php?id=39

 

세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.

 

{20, 48, 52}, {24, 45, 51}, {30, 40, 50}

 

p가 1000이하일 때, 세변의 길이가 모두 자연수인 직각삼각형을 가장 많이 만들 수 있는 p의 값은 얼마입니까?

오일러 프로젝트 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) 와 곱한 결과들을 모아서 팬디지털이 되는지 검사한다. 즉 문제의 내용 그대로를 코딩하면 된다.

  1. 임의의 수 n에 대해서
  2. 1, 2, 3..을 차례로 곱해나가면서, 곱한 값을 연결한다.
  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 번 문제는 순환소수와 약간 비슷하지만, 의외로 성가신 구석이 매우 많은 문제이다. 동시에 잘 설계된 가드가 얼마나 수행 속도를 빠르게 만들어줄 수 있는지에 대한 좋은 예이기도 하다.

오일러 프로젝트 37 더보기

오일러 프로젝트 36

오일러 프로젝트 36 번은 대칭수에 대한 문제이다. 대칭수는 이전에도 몇 번 나왔던 문제이다.

대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요. (주의: 첫번째 자리가 0이면 대칭수가 아님)

http://euler.synap.co.kr/prob_detail.php?id=36

오일러 프로젝트 36 더보기