RSS Feed

최적 특수합 집합의 원소를 한 문자열로 나열하면?

Problem 103

출제 일시 : 2013-01-29 16:47:07, ☕ 9

크기가 n인 집합 A의 원소들을 모두 더한 값을 S(A)라고 합시다. A의 부분집합 중 공집합이 아니면서 서로소인 임의의 두 집합 B, C가

  1. S(B) ≠ S(C)
  2. B가 가진 원소의 개수가 C보다 많다면 S(B) > S(C)

라는 두 가지 조건을 만족하면 이 집합을 '특수합 집합'이라고 부르겠습니다.

크기 n인 특수합 집합 A 중 S(A)가 가장 작은 특수합 집합을 '최적 특수합 집합'이라고 합시다. n=1~5까지 최적 특수합 집합을 나열해 보면 다음과 같습니다.

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= {a1, a2, ..., an} 다음에 나올 최적 특수합 집합 B는 B={b, a1+b, a2+b, ..., an+b}의 형태로 만들어진다고 추측할 수 있습니다(여기서 b는 집합 A의 가운데 항입니다).

위 "법칙"으로 n=6일 때 최적 특수합 집합을 구해보면 A= { 11, 17, 20, 22, 23, 24}가 되고, S(A)=117인 것처럼 보입니다. 하지만 이건 이전 집합에 근거한 귀납적 알고리즘으로 얻은 집합일 뿐 최적 특수합 집합이 아닙니다. n=6일 때 최적 특수합 집합은 A = {11, 18, 19, 20, 22, 25}가 되고, S(A)=115입니다. A의 모든 원소를 문자열 형태로 쭉 나열하면 111819202225가 되겠죠.

 

n=7일때 최적 특수합 집합 A를 구하고, 그 원소를 문자열 형태로 나열하십시오.

주) 이 문제는 105번과 106번 문제와 관련되어 있습니다.

 

 


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.