놀이공원 인형 맞추기

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

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

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

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

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

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


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

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

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]);
}

}


※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
우선은 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이 되는 세개의 숫자중 세번째 숫자




    }

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

풀이 작성

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

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


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