[ day 5 ] 수열 복원

수열 복원

• 시간 제한: 1 초

양의 정수로 이루어진 수열 a1​,a2​,⋯,an​이 있습니다.

1≤ai​≤105

이 수열에서 각 원소를 선택하거나 선택하지 않음으로써 총 2n개의 부분 수열을 만들 수 있고, 만들어진 모든 부분 수열의 합인 2n개의 정수가 주어졌을 때, 원래의 수열 a1​,a2​,⋯,an​을 구하는 프로그램을 작성하세요.

 

 

지시사항

입력

• 첫째 줄에 정수 n이 주어집니다.
  
  1≤n≤15
• 둘째 줄에 이 수열에서 만들 수 있는 모든 부분 수열의 합인 2n개의 정수 s1​,s2​,⋯,s2n​이 주어집니다.
  
  0≤si​≤n×105

출력

• 첫째 줄에 원래 수열의 원소를 오름차순으로 출력합니다.

입력 예시

3
1 4 7 3 0 6 5 2

출력 예시

1 2 4

 

 

 

작성 코드 

import math
import itertools

n = int(input())

data = list(map(int,input().split()))

# target 을 몇개의 숫자로 만들지
def find_int(target,num_int):
    combinations = []

    for i in itertools.combinations_with_replacement(range(1, target+1), num_int):
        if sum(i) == target:
            combinations.append(i)
            # print("target" , target)
            # print("num_int",num_int)
            # print(i)
            # print()
    
    # print("target" , target)
    # print("num_int",num_int)
    # print(combinations)
    # print()
    return combinations
    

Possibilities = []

for i in data:
    for j in range(1,n+1):
        Possibilities.append(find_int(i,j))


print(Possibilities)

 

이건 완전탐색쪽으로 가면 될것 같다라고 생각하여 각 숫자를 이루어 낼 수 있도록 더 하기 가능한 모든 경우수를 찾는식으로 접근했었다. 그러나 해당 방법은 아니라고 생각하였고, 주어진 힌트 N에 좀 더 집중해서 접근해보기로 했다.

import itertools

n = int(input())

data = list(map(int,input().split()))

data.sort()

check = [data[1]] # 0은 아님

# itertools.combinations_with_replacement(range(1, target+1), num_int))

for i in range(1,len(data)):
    can_ = False
    for j in range(1,n+1):
        for k in itertools.combinations_with_replacement([0,1], j):
            if len(k) > len(check):
                continue
            
            total = 0
            for z in range(len(k)):
                if k[z] == 1:
                    total += check[z]
            
            if total == data[i]:
                can_ = True
                break
        if can_ == True:
            break
    if can_ == False:
        check.append(data[i])
        if len(check) == n:
            break

for i in check:
    print(i,end=" ")

 

뭔가 솔트해서 풀어나갈수 있을것 같다는 생각이 들었다.

 

 

접근을 새롭게 해보았다.

import itertools

n = int(input())

data = list(map(int,input().split()))

data.sort()

oh = []

for i in data:
    if i == 0:
        continue 
    check = False
    for j in range(2,len(oh)+1):
        for k in itertools.combinations(oh,j):
            if sum(k) == i:
                check = True
    
    if check == False:
        oh.append(i)
        if len(oh) == n:
            break
for i in oh:
    print(i,end=" ")

 

sort를 하면 사실상 원소가 작은 수가 먼저 나오는것일테니 원래 원소가 순서대로 등장할 것이다.

 

그렇다는건 양의 정수이므로 총합이 0인 경우는 모든 원소를 선택하는 것 밖에 없을테니 0은 건너 뛰고,

차례로 작은 수 부터 살펴본다면 해당 수보다 작은 수들로 그 수가 만들어지지 않는다면 그건 원래 원소인 것이다.

 

 

근데 2개의 문제가 틀린게있었다. 뭐가 잘못되었지? 생각했다가.

 

아 같은 수가 있을경우를 내가 고려안했다는걸 깨달았다.

 

import itertools

n = int(input())

data = list(map(int,input().split()))

data.sort()

oh = []
past = -1
for i in data:
    if past == i:
        oh.append(i)
        if len(oh) == n:
            break
        else:
            continue
    if i == 0:
        continue 
    check = False
    for j in range(2,len(oh)+1):
        for k in itertools.combinations(oh,j):
            if sum(k) == i:
                check = True
    
    if check == False:
        oh.append(i)
        if len(oh) == n:
            break
    past = i
for i in oh:
    print(i,end=" ")

 

무식하지만 past를 통해 동일한 숫자가 나왔는가? 를 판단한다. 

최종 100점 통과 완료하였다. 근데 알다싶이 너무 하드코딩이다. 제대로된 알고리즘을 공부해야겠다고 생각했다.

 

정답 코드

C++

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, a, ans;
vector<ll>v, res;
multiset<int>now;
void dfs(ll x, ll sum) {
    if (x == res.size()) {
        now.insert(sum + m);
        return;
    }
    dfs(x + 1, sum);
    dfs(x + 1, sum + res[x]);
}
void solve() {
    cin >> n;
    for (int i = 0; i < (1 << n); i++) {
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    for (int i =1; i < v.size(); i++) {
        
		if (now.find(v[i]) == now.end()) {
			m = v[i];
			dfs(0, 0);
			res.push_back(v[i]);
		}
		now.erase(now.find(v[i]));
    }
    for (auto nxt : res)cout << nxt << ' ';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}

Python

import sys
from itertools import combinations

def dfs(res, x, sum_, now, m):
    if x == len(res):
        now.append(sum_ + m)
        return
    dfs(res, x + 1, sum_, now, m)
    dfs(res, x + 1, sum_ + res[x], now, m)

def solve():
    n = int(input())
    v = list(map(int, input().split()))
    v.sort()
    res = []
    now = []
    for i in range(1, len(v)):
        if v[i] not in now:
            m = v[i]
            dfs(res, 0, 0, now, m)
            res.append(v[i])
        now.remove(v[i])
    print(' '.join(map(str, res)))

if __name__ == "__main__":
    solve()

Java

import java.util.*;

public class Main {

    static ArrayList<Long> res = new ArrayList<>();
    static ArrayList<Long> now = new ArrayList<>();

    public static void dfs(ArrayList<Long> res, int x, long sum_, ArrayList<Long> now, long m) {
        if (x == res.size()) {
            now.add(sum_ + m);
            return;
        }
        dfs(res, x + 1, sum_, now, m);
        dfs(res, x + 1, sum_ + res.get(x), now, m);
    }

    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Long> v = new ArrayList<>();

        for (int i = 0; i < (1 << n); i++) {
            long a = scanner.nextLong();
            v.add(a);
        }

        Collections.sort(v);

        for (int i = 1; i < v.size(); i++) {
            if (!now.contains(v.get(i))) {
                long m = v.get(i);
                dfs(res, 0, 0, now, m);
                res.add(v.get(i));
            }
            now.remove(v.get(i));
        }

        for (long nxt : res) {
            System.out.print(nxt + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        solve();
    }
}