취미가 알고리즘

문제

풀이

이 문제는 방법이 다양한것 같았습니다. dfs로 푸신분들도 계셨지만 저는 최근에 그리디를 좀 많이 풀었어서 그런지 그리디로 먼저 접근했습니다.

우선 수열이 a1, a2, a3, ... an 까지 존재한다고 했을 때 이 수열의 부분수열의 합을 2^n개 만들 수 있습니다.

하지만 문제에서 주어지는 입력은 그 부분수열의 합인 2^n개의 수가 주어집니다.

따라서 어떤 수열의 조합으로 입력되는 부분 수열의 합을 만들 수 있는지 원래 수열의 원소들을 구하는 문제입니다.

처음 생각해본건 두가지입니다.

1. 입력으로 주어지는 수열 중 0은 절대 답이 될 수 없음

2. 0 다음으로 제일 작은 수는 무조건 원래 수열의 원소에 해당함

1번은 원래 수열의 원소 ai의 범위는 1 ~ 100000입니다. 0을 만들려면 어떤 원소도 더하지 않는 경우밖에 없습니다.

2번은 0 다음으로 제일 작은 수는 어떤 수를 더하더라도 만들 수 없습니다. 그냥 자신만이 그 수를 만들 수 있습니다.

0 다음으로 제일 작은 수가 여러개라면 그 같은 수들을 모두 더해주도록 합니다.

여기서 시작해서 어떻게 그리디하게 접근할 수 있을까 고민하다가 map과 set을 사용하게 되었습니다.

map과 set에는 원래 수열로 인해 제거되는 부분 수열의 값을 저장합니다.

제가 수를 제거한 방식으로는

set에 지금까지 모은 원래 수열의 부분 수열의 합을 모두 다 저장합니다.

map에는 set에서 구한 합들을 카운팅합니다.

예를들어 지금까지 구한 원래 수열이 1, 2, 3라고 했을 때 얘내들의 부분 수열의 합은 0 1 2 3 3 4 5 6 입니다.

그리고 다음 추가되는 원소가 4라고 했을 때 원래 수열은 1, 2, 3, 4가 되고,

이전에서 구했던 부분 수열의 합에서 모두 +4를 해주면 4 5 6 7 7 8 9 10이 되는데,

이걸 부분 수열의 합으로 모두 추가하면 0 1 2 3 3 4 4 5 5 6 6 7 7 8 9 10이 되고, 이는 수열 1, 2, 3, 4의 부분 수열의 합이 됩니다.

위에서 구한 값들을 set과 map에 넣어주고,

다음 들어오는 값을 key로 map에 검색하여 1 이상으로 카운팅되어 있다면 선택하지 않고 넘어가는 방식입니다. 이때 map[key]를 1씩 감소시킵니다.

여기서 map을 사용한 이유는 원래 수열의 원소를 원래 수열의 합으로 만들 수도 있기 때문입니다.

2 4 6이 원래 수열이라면 2 + 4로도 6을 만들 수 있기 때문에 6이 걸러지는 문제가 있었습니다. 덕분에 코드가 더러워졌습니다...

map에서 카운팅한 만큼의 수를 걸러내고, 제거되지 않은 수들 중 제일 작은 수를 순서대로 넣어주면 원래 수열을 구할 수 있습니다.

코드