놀이공원 인형 맞추기

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

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

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

가령 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

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

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

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)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
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=" ")

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

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
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 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]])
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
우선은 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



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

package codingdojang;

import java.util.Scanner;

public class doll {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner s=new Scanner(System.in);

    int dollCnt=s.nextInt();
    int dollSum=s.nextInt();
    int arr[]=new int[dollCnt];
    for(int i=0;i<dollCnt;i++){
        arr[i]=s.nextInt();
    }
    int n1=0,n2=0,n3=0;
    for(int i=0;i<10;i++){
        for(int j=i+1;j<10;j++){
            for(int k=j+1;k<10;k++){
                if(arr[i]+arr[j]+arr[k]==50){
                    n1=i;
                    n2=j;
                    n3=k;
                    break;
                }
            }
        }
    }
    System.out.println(arr[n1]+" , "+arr[n2]+" , "+arr[n3]);
}

}


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

javascript

주어진 수열을 가지고 만들 수 있는 모든 조합을 생성한 후,

합이 50이 되는 것을 필터링하고

소트해서 보여줍니다.

var input = 
`10 50
25 27 3 12 6 15 9 30 21 19`;

var [[count, sum], dolls] = input.split("\n").map($ => $.split(" ").map($ => parseInt($)));

var combination = function combination(array){
    if (array.length === 0)
        return [[]];
    var combs = [];
    for (var i = 0; i <= array.length; i++){
        var head = array.slice(i, i + 1),
            tail = array.slice(i + 1),
            tailcombs = combination(tail);
        combs.push(...tailcombs.map($ => head.concat($)))
    }
    return combs;
};

var result = combination(dolls).filter($ => $.reduce((a, b) => a + b, 0) === sum)
                               .map($ => $.sort((a, b) => a - b));

console.log(result.map($ => $.join(" ")).join("\n"));
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

array = input("input number array : ")
tgt = input("input target sum : ")


array = [int(x) for x in array.split(" ")]
result = []
result_list = []

for i in range(0,len(array)):
    for j in range(i+1,len(array)):
        for k in range(j+1,len(array)):
            if (array[i] + array[j] + array[k]) == int(tgt):
                result = sorted([array[i], array[j], array[k]])
                result_list.append(result)


for l in range(0,len(result_list)):
    for m in range(l+1,len(result_list)):
        if result_list[l] == result_list[m]:
            del(result_list[m])
            break


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

Python3

shoot()은 맞춘 인형 중 가장 숫자가 큰 인형을 뽑는 함수입니다.

예를 들어 인형이 1 2 3 4 5 가 있다고 할 떄,

숫자가 큰 인형부터 맞춘다고 가정하면(결과가 숫자의 조합이기 때문에 무리 없는 가정)

첫 번쨰로 5를 맞춘 경우, 첫 번째로 4를 맞춘 경우, ... 1을 맞춘 경우가 생깁니다.

요점은 지금 맞춘 인형이 "가장 숫자가 큰" 인형이기 때문에 그보다 숫자가 큰 인형을 제외할 수 있습니다.

즉 첫 번째로 5를 맞췄으면 두 번째 숫자가 큰 인형은 1 2 3 4 중 하나,

첫 번째로 4를 맞췄으면 다음에는 1 2 3 중 하나,

첫 번쨰로 3을 맞췄으면 다음에는 1 2 중 하나,

첫 번째로 2를 맞췄으면 다음에는 1 이 됩니다.

물론 합이 다 찼으면 다음으로 넘어가지 않고 중단합니다.

def shoot(dolls, sum, hits):
    if sum == 0: return hits
    if sum < 0: return None

    while dolls:
        hit = dolls.pop()
        ret = shoot(dolls[:], sum - hit, [hit] + hits)
        if ret: return ret
    return None

inp = '''10 50
25 27 3 12 6 15 9 30 21 19'''

inp = list(map(int, inp.split()))
print(shoot(sorted(inp[2:]), inp[1], [])) # 6 19 25

만약 인형 개수가 정해져 있어서 위의 재귀함수를 for문으로 처리한다면 이런 형태가 됩니다.

for i in range(len(dools)):
    for j in range(i+1, len(dools)):
        for k in range(j+1, len(dools)):
            ...
                if dools[i] + dools[j] + dools[k] + .... == sum:
                    return [..., dools[k], dools[j], dools[i]]
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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


언어별 풀이 현황
전 체 x 20
java x 5
python x 9
기 타 x 2
ruby x 1
cs x 1
matlab x 1
javascript x 1