놀이공원 인형 맞추기

놀이공원에 가면 인형 맞추기 게임이 있다.

한 놀이공원에는 인형에 숫자를 써놓고 인형 맞추기를 한다.

그런데 맞춘 인형의 숫자의 합이 특정한 값이 되는 경우에만 맞춘 인형을 가져 갈 수 있다.

가령 10개의 인형에 쓰여진 숫자가 각각 25 27 3 12 6 15 9 30 21 19이고 숫자의 합이 50이 되는 경우만 인형을 가져갈수 있다면 6 19 25가 쓰여진 인형을 맞춰야 인형을 가져 갈 수 있다.

이때 인형의 갯수와 각각의 숫자와 필요한 합을 입력받으면 맞춰야 하는 인형의 숫자를 출력하는 프로그램을 작성해 보자.

입력 - 첫줄에는 인형의 갯수와 필요한 합, 둘째줄에는 인형 각각에 쓰여진 숫자

예)

10 50

25 27 3 12 6 15 9 30 21 19

출력 - 필요한 합이 되는 인형 각각의 숫자를 오름차순으로 출력

예)

6 19 25

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

15개의 풀이가 있습니다. 1 / 2 Page

우선은 brute-force 방법으로 MATLAB 짜보았습니다

clear all
close all
clc

t_start=clock;

% brute-force combination


%% input values

input_val1=str2num(input('인형갯수 필요한합 ','s'));
dolls_N=input_val1(1);
target_sum=input_val1(2);

dolls_input=str2num(input(sprintf('인형숫자들 (%d개) ',dolls_N),'s'));


%% find the combinations 
dolls_sorted=sort(dolls_input,'ascend');

% length would be 2^N, where N is the number of the dolls
solution_cnt=0;
solution_arr_aloc=cell(2^dolls_N,dolls_N);

% find all combination
% example, if there are 3 numbers, the combination would be 2^3 - 1 = 7
% X X O
% X O X 
% O X X
% X O O
% O X O
% O O X
% O O O

for n=1:2^dolls_N-1

    % at this combination, collect the index numbers
    test_array=[];
    tmp=n;
    for p=dolls_N:-1:0
        if tmp >= 2^p
            test_array=[test_array p+1];
            tmp=tmp-2^p;
        end
    end

    % if the sum of the selected dolls is equal to the target num, save it
    if sum(dolls_input(test_array))==target_sum
        solution_cnt=solution_cnt+1;
        solution_arr_aloc{solution_cnt}=dolls_input(test_array);
    end
end

refined_solution_arr_aloc=cell(solution_cnt,dolls_N);
for q=1:solution_cnt
    refined_solution_arr_aloc{q}=solution_arr_aloc{q};
end
clear solution_arr_aloc

%% show the result
disp(['number of combinations : ' num2str(solution_cnt)]);
for q=1:solution_cnt
    sort(refined_solution_arr_aloc{q},'ascend')
end


%% show the elapsed time
t_finish=clock;
elapsed_time=etime(t_finish,t_start);

if elapsed_time<60
    disp(['    elapsed time : ' num2str(elapsed_time) ' sec']);
elseif elapsed_time<3600
    disp(['    elapsed time : ' num2str(elapsed_time/60) ' mins']);
else    
    disp(['    elapsed time : ' num2str(elapsed_time/3600) ' hours']);
end



※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def doll(data):
    n,limit=data[0]
    data=sorted(data[1])
    if sum(data)<limit or min(data)>limit:
        return -1
    for i in range(n):
        if data[i]==limit:
            return [data[i]]
        elif doll([[n-1,limit-data[i]],data[0:i]+data[i+1:]])==-1:
            pass
        else:
            return [data[i]]+doll([[n-1,limit-data[i]],data[0:i]+data[i+1:]])
    return -1
doll([[10,50],[25, 27, 3, 12, 6, 15, 9, 30, 21, 19]])
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AmusementPark {

    public static void main(String[] args) throws FileNotFoundException {
        String path = AmusementPark.class.getResource("").getPath();
        Scanner sc = new Scanner(new File(path + "AmusementPark.txt"));

        int size = sc.nextInt();
        int target = sc.nextInt();
        int[] dolls = new int[size];

        for (int i = 0; i < size; i++) {
            dolls[i] = sc.nextInt();
        }

        for (int i = 1; i < 1 << size; i++) {
            int k = i;
            int d = 0;
            List<Integer> t = new ArrayList<>();
            while (k > 0) {
                if (k % 2 == 1) t.add(dolls[d]);
                k = k / 2;
                d++;
            }
            if (t.stream().mapToInt(Integer::intValue).sum() == target) {
                System.out.println(t);
            }
        }
    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def sublist_(a):
    sublist=list()
    result=[]
    for i in range(1,1<<len(a)):
        k=str(bin(i))
        r=0
        for j in reversed(k[2:]):
            if j=="1":
               sublist.append(a[r])
            r+=1
        result.append(sublist)
        sublist=[]
    return result
a,b=map(int,input().split(" "))
setlist=list(map(int,input().split(" ")))
setlist_=sublist_(setlist)
for i in setlist_:
    if sum(i)==a:
        print(i,end=" ")

전체 부분 집합을 만들고 합을 구해서 같으면 출력합니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

subsquence를 뽑아낼 때 재귀를 사용했습니다. 파이썬 3을 사용하였습니다.

def combination(x):
    if len(x)==1:
        return [[x[0]]]
    else:
        smallercombi=combination(x[:len(x)-1])
        realcombi=smallercombi[:]
        for smaller in smallercombi:
            realcombi.append(smaller+[x[len(x)-1]])
        realcombi.append([x[len(x)-1]])
        return realcombi

numofdoll, target =  map(int, input("두 수를 공백으로 구분하여 입력하시오 : ").split())
numlist = []
for x in range(numofdoll):
    numlist.append(int(input("인형에 써진 수를 입력하시오 : ")))
subsequence = combination(numlist)
for sub in subsequence:
    if sum(sub) == target:
        sub.sort()
        print(sub)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import java.util.Random;* 

public class DollHitter {

    public static void main(String args[]){

    int num = 15;
    int sum = 60;
    Random ran = new Random();

    int arr[] = new int[num];
    for(int i = 0 ; i < num ; i++){

        arr[i] = ran.nextInt(30)+1;
        for(int j = 0 ; j < i ; j++){
            if(arr[i] == arr[j]){
                i--;
            }
        }
    }
    중복되지 않는 30 이하 난수 15개 생성 (제한 포인트는 맘대로 지정하셔도 됩니다)

    for(int i = 0 ; i < arr.length ; i++){
        System.out.print(arr[i]+" : ");
    }

    int set[] = {};

    for(int i = 0 ; i < arr.length ; i++){
        set = new int[3];
        set[0] = arr[i];
        for(int j = i+1 ; j < arr.length ; j++){
            set[1] = arr[j];
            for(int k = j+1 ; k < arr.length ; k++){
                set[2] = arr[k];
                if(set[0]+set[1]+set[2] == sum){
                    System.out.println(set[0]+" : "+set[1]+" : "+set[2]);
                }

            }
        }

    }

    바깥 for문은 생성된 난수 배열의 합이 60이 되는 세개의 숫자중 첫번재 숫자
    중간 for문은 생성된 난수 배열의 합이 60이 되는 세개의 숫자중 두번재 숫자
    안쪽 for문은 생성된 난수 배열의 합이 60이 되는 세개의 숫자중 세번째 숫자




    }

}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
len_, sum_ = map(int, input(":").split(' '))
list_ = list(map(int, input(":").split(' ')))
result = [sorted(x) for x in [[list_[i] for i in range(len(list_)) if j & (1 << i)]
                              for j in range(1, 1 << len(list_))]
              if sum(x) == sum_]
print('\n'.join([','.join(map(str, x)) for x in result]))

Python 3.5.2에서 작성하였습니다.
bit연산으로 부분집합을 구해서 풀었습니다.

와 정말 뭐가뭔지 모르겠어요. 혹시 여유가 되시면 bit 연산을 어떻게 응용했는지 설명좀 부탁드립니다. - Dr.Choi, 2017/01/10 00:48 M D
전체 부분 집합을 만드는 방법이 진짜 신박한데 너무 궁금해요!!!! - Dr.Choi, 2017/01/10 01:55 M D
무식하게 풀었는데 감사합니다..^^;; 배열 수 만큼의 길이의 bit를 나열하고 1 이되는 자리수의 값을 배열로 묶어서 부분집합을 만들었습니다. [0, 1, 2] 1 : 0 0 1 : [2] 2 : 0 1 0 : [1] 3 : 0 1 1 : [1, 2] 4 : 1 0 0 : [0] 5 : 1 0 1 : [0, 2] 6 : 1 1 0 : [0, 1] 7 : 1 1 1 : [0, 1, 2] - Yeo HyungGoo, 2017/01/10 09:41 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

입력을 다 처리했다 치면 main()은 아래처럼 만들어볼 수 있다.

int main(int argc, const char * argv[]) {
    int ns[] = {25,27,3,12,6,15,9,30,21,19};
    nsum(ns, 10, 50);
    return 0;
}

nsum()은 숫자들로 합계를 만들어보고 가능하면 그 값들을 출력해준다.

마치 여러가지 동전들로 특정 금액 만드는 문제와 비슷하다. 처음부터 하나씩 넣어보고(dfs) sum을 만들어보자.

void nsum(int ns[], int len, int sum) {
    int* answer = (int*)malloc(sizeof(int) * len);

    int* answer2 = dfs(ns, len, 0, answer, sum); // 0번부터 시작!
    if (answer2) {
        for (int* i=answer; i < answer2; i++) {  // 답을 찾았으면 숫자들 출력
            printf("%d ", *i);
        }
        printf("\n");
    } else {
        printf("impossible\n");
    }

    printf("%d steps\n", step); // 184
    free(answer);
}

dfs는 i번째 위치의 숫자를 넣는 경우와 넣지 않는 경우로 모든 경우를 검사한다. 그전에 재귀의 끝을 확인한다.

int* dfs(int ns[], int len, int i,
         int* answer, int sum) {
    if (sum == 0) // 답을 찾았다!
        return answer;
    if (i == len) // 더이상 처리할 숫자가 없다.
        return 0;

    // i를 넣거나
    *answer = ns[i];
    int *answer2 = dfs(ns, len, i+1, answer+1, sum-ns[i]);
    if (answer2) return answer2;

    // 넣지 않거나
    return dfs(ns, len, i+1, answer, sum);
}

그런데, 이러면 모든 경우를 살펴보는 것이고.. 미리 숫자가 정렬되어 있으면 앞으로 만들어야하는 합보다 남은 숫자들이 더 큰 경우 더 이상 테스트해볼 필요가 없다. (예, 10을 만들어야 하는데 11, 12, 13..이 남았다면 11뿐만 아니라 12, 13도 살펴볼 필요가 없다)

미리 정렬 해 놓고,

int intComp(const void* a, const void* b) {
    return *(int*)a == *(int*)b ? 0 : *(int*)a > *(int*)b ? 1 : -1;
}

void nsum(int ns[], int len, int sum) {
    qsort(ns, len, sizeof(int), intComp);
    ...
}

dfs()에서 만들 sum이 현재 값 ns[i]보다 작으면 i 뒤로는 볼 필요없다.

int* dfs(int ns[], int len, int i,
         int* answer, int sum) {
    if (sum == 0) // 답을 찾았다!
        return answer;
    if (i == len) // 더이상 처리할 숫자가 없다.
        return 0;
    if (ns[i] > sum) // i 뒤로는 볼 필요 없다.
        return 0;

    ...
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
using System;
using System.Collections;
using System.Collections.Generic;

namespace CodingTest
{
    class Program
    {
        private static int sum = 50;
        private static int[] entities = new int[] { 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 };
        private static List<string> itemSet = new List<string>();

        static void Main(string[] args)
        {
            Array.Reverse(entities);
            for (int i = 0; i < entities.Length; i++)
            {
                checkToSum(i);
            }
            foreach (string im in itemSet)
            {
                Console.WriteLine(im);
            }
            Console.ReadLine();
        }

        static void checkToSum(int startIdx)
        {
            int targetInt = sum - entities[startIdx];
            int parentInt = 0;
            int childInt = 0;
            for (int i = 0; i < entities.Length; i++)
            {
                if (entities[i] == entities[startIdx] || parentInt == entities[startIdx]) continue;
                if (parentInt == 0) parentInt = entities[i];
                childInt = entities[i];
                if (parentInt == childInt) continue;
                if (targetInt == parentInt + childInt)
                {
                    ArrayList ax = new ArrayList();
                    ax.Add(entities[startIdx]);
                    ax.Add(parentInt);
                    ax.Add(childInt);
                    ax.Sort();
                    string result = string.Format("{0} {1} {2}", ax[0], ax[1], ax[2]);
                    if (itemSet.FindAll(x => x == result).Count == 0)
                        itemSet.Add(result);
                    return;
                }
            }
        }
    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬3.5

죄송합니다... 위 댓글에는 지적질을 했는데 정작 제풀이는 형편이 없습니다.
속도도 최악입니다. 어떻게 손을 써볼수가 없었습니다.
입력, 출력 풀어조건에도 맞질 않습니다. 속도가 느리니 즐겁지가 않아 여기까지만 했습니다.

def f(a, target):

    a = sorted(a)
    result = set()

    def g(a):

        if sum(a) == target:
            result.add(tuple(a))
            return

        elif sum(a) < target:
            return

        else:
            for i in range(len(a)):
                x = a[:i] + a[i+1:]
                g(x)

    g(a)

    return result


a = [25, 27, 3, 12, 6, 15, 9, 30, 21, 19]
target = 50
f(a, target)

파이썬3.4.3

위의 방식보다 획기적으로 속도개선을 했습니다. 그러나 느리지요. 왜냐하면 완전탐색이니까요ㅜㅜ
보다 나은 알고리즘을 공부하면 다시 올리겠습니다.

# 제출 코드

# 입력
n, goal = tuple(map(int, input().split()))
a = sorted(list(map(int, input().split())))
assert len(a) == n

# 처리
result = []
def shot(last=0, picked=None, score=0):

    global result

    if picked is None:
        picked = []

    # 기저사례
    if score == goal:
        return picked

    elif score > goal:
        return False

    for i in range(last, n):      
        picked.append(a[i])
        ret = shot(i+1, picked, score+a[i])
        if ret: result.append(ret[:])    # result.append(ret)는 빈값이 됨.
        picked.pop()

# 출력
shot()
for line in result:
    for case in line:
        print(case, end=' ')
    print()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 15
matlab x 1
python x 6
java x 4
기 타 x 2
cs x 1
ruby x 1