Project Euler #103 (Special subset sums: optimum)

문제는 https://projecteuler.net/problem=103

그러나 사실 103번은 맛보기고 105번과 106번이 진짜 문제라고 할 수 있다.

103번은

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

에서

A = {a₁, a₂, ... , a_n}라는 optimum set이 있을 때, 다음 optimum set은 B = {b, a₁+b, a₂+b, ... ,a_n+b}, (이때 b는 A의 중간 원소) 이라서

n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117 일 것 같은데 실제로는 

n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 가 된다는 것이다.

그럼 n = 7일때는 뭘까? 라고 물어본다.

처음 접근하려고 보면 하.. 역시 규칙있는 척 하다가 결국 코딩으로 풀란 문제구나 싶다.

하지만 실제로는 아주 간단하게 풀어진다.

n = 5에서 n = 6으로 넘어갈 때 규칙이 적용되지 않는 이유는, 원소가 짝수개가 되기 때문이다.(!)

이게 무슨 소린고 하니..

A(6) = {a₁, a₂, ... , a₆} 를 잡으면

(나중에 105번이나 106번 문제에서 자세히 살펴보게 되겠지만)

{a₁ + a₅ + a₆} v.s. {a₂ + a₃ + a₄} 등 개수가 같을 때 비교해야 되는 경우가 발생한다.

사실 A = {a₁, a₂, ... , a_n}라는 optimum set이 있을 때, 다음 optimum set은 B = {b, a₁+b, a₂+b, ... ,a_n+b}로 잡는 이유는

원소 b를 제외한 {a₁+b, a₂+b, ... ,a_n+b} 가 rule i, ii를 만족할 것이라는 기대가 있다. (subset이 rule i, ii를 만족해야 하므로)

그래서 n = 6의 optimum set을 구하는 것은 일단 생각하지 말자.

그럼 n = 7의 optimum set이 뭘까 한번 "찍어보자" (표현이 좀 그렇지만 완전히 코딩해서 풀지는 않았기 때문에..)

A = {a₁, a₂, ... , a_n}라는 optimum set이 있을 때, 다음 optimum set은 B = {b, a₁+b, a₂+b, ... ,a_n+b}

그런데 이때 b가 A의 중간 원소라는 것은 사실이 아니다.

다만 새롭게 set을 만들었으므로 7개의 원소가 크기가 작은것부터 큰것으로 정렬되어 있을때

처음 4개의 원소, 즉 {b, a1+b, a2+b, a3+b}의 합이 뒤 3개의 원소 {a4+b, a5+b, a6+b}보다 커야한다. (rule ii에 의해서)

(b + a1+b + a2+b + a3+b) > (a4+b + a5+b + a6+b) 가 되게 되는데,

4b + a1 + a2 + a3 > 3b + a4 + a5 + a6로 정리되므로

b > a4 + a5 + a6 - a1 - a2 - a3 로 다시 정리할 수 있다.

이때 {a1, a2, a3, a4, a5, a6}은 {11, 18, 19, 20, 22, 25}였다는 것을 잊지말자.

따라서 b > (20+22+25-11-18-19) = 19가 되면서 b >= 20 즉 b가 20일 때가 최소일 것으로 기대하고 테스트할 가치가 생긴다.

그럼 가장 먼저 테스트해봐야 되는 set은

{20, 31, 38, 39, 40, 42, 45}가 된다.

음... 한번 찍어보라.

이제 105번과 106번을 풀어보자.

105번보다 106번을 먼저 푸는것이 도움이 될 것이다.