놀이공원 인형 맞추기

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

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

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

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

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

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

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

(수정)

디디님 너무 좌절하시는 거 같아서....

N개의 숫자에 대해서 임의의 A개의 숫자를 골라 더할 수 있는 경우는 2^N이고, 전체 케이스를 완전 탐색한다고 하면, 지수적 시간복잡도를 갖는 문제이고, 다항 시간 내에 풀기도 쉽지 않을 것 같습니다. 만약 문제에서 "전체 조합을 구하라" 같은 조건이 명시돼 있었다고 가정하면...

만약 입력된 숫자들이 오름차순으로 정렬되어 있다고 할 때 작은 숫자부터 우선 선택하며, 선택한 숫자의 개수도 작도록 숫자를 선별합니다. K 개의 숫자를 골라서 고른 숫자의 합이 S보다 작으면 버리고, 일치하면 줍습니다. 그리고 S보다 크면 K개 조합의 그 이후 버전은 다 볼필요가 없으므로 건너뛸만하겠죠.

이런식으로 볼 필요가 없는 부분들을 빼고 검사해나가면 좀 더 빠르게 풀 수 있습니다만, 숫자의 개수가 아주 많고, 1, 2, 3 등 작은 값들의 비율이 크고 S가 꽤 큰 값이라면 이것 역시 시간이 오래 걸릴 수 밖에 없습니다.

from itertools import combinations

def do2(n, xs):
    result = []
    xs.sort()
    for i in range(2, len(xs)+1):
        cb = combinations(xs, i)
        for ys in cb:
            if sum(ys) == n:
                result.append((*ys,))
            elif sum(ys) > n:
                break
    return [sorted(x) for x in result]

def main2():
    n, s = [int(x) for x in input().split()][:2]
    xs = [int(x) for x in input().split()][:n]
    result = do2(s, xs)
    print("\n".join(str(x) for x in result))
    print('done')

# >>> 344 1888
# >>> 2 9 11 12 14 17 20 22 25 26 28 33 36 44 50 52 59 61 66 79 80 88 91 93 94 96 102 103 104 109 113 118 120 128 132 134 136 137 145 147 148 149 154 157 158 162 163 166 168 169 172 173 174 176 178 179 180 181 184 193 195 196 199 201 202 210 213 216 217 218 221 232 235 236 237 244 248 250 251 252 253 257 260 264 268 277 278 287 289 291 293 299 301 302 303 304 305 306 308 317 319 322 325 328 329 330 332 333 338 342 345 349 351 355 356 357 358 359 360 364 366 369 370 371 372 375 383 384 386 390 396 399 400 402 403 404 409 412 413 415 417 419 424 425 426 443 444 447 448 449 454 457 463 465 469 471 478 479 480 482 486 487 490 492 497 498 499 502 504 506 512 513 518 520 521 522 525 526 533 537 538 540 543 547 551 553 555 556 558 559 562 566 567 572 574 575 577 580 581 582 583 585 590 594 598 599 600 603 604 610 612 615 625 628 633 635 639 643 644 651 652 654 655 658 660 664 665 667 669 673 676 678 680 684 685 687 688 689 690 691 695 696 700 702 706 712 718 719 721 722 724 726 727 732 734 735 739 740 745 746 750 751 752 753 754 755 757 759 761 765 766 767 771 773 777 782 783 785 790 794 795 799 812 815 819 821 823 826 827 830 833 838 845 846 847 848 850 851 856 857 858 862 867 868 876 878 880 883 890 892 900 908 910 914 917 918 919 921 922 923 924 930 932 937 940 946 947 949 952 954 959 961 969 971 973 977 978 979 982 986 988 990 994 999

[2, 9, 878, 999]
[2, 9, 11, 867, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 782, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 757, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 590, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 540, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 302, 999]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 232, 990]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 80, 88, 91, 93, 94, 96, 680]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 80, 88, 91, 93, 94, 96, 102, 103, 104, 371]
[2, 9, 11, 12, 14, 17, 20, 22, 25, 26, 28, 33, 36, 44, 50, 52, 59, 61, 66, 79, 80, 88, 91, 93, 94, 96, 102, 103, 104, 109, 113, 149]

done 
( 959 ms )


역시나 속도는 할말 없습니다;;; python3.5입니다.

def do(s, xs):
    if s == 0:
        return [], True
    for i, x in enumerate(xs):
        ys = xs[:i] + xs[i+1:]
        zs, r = do(s-x, ys)
        if r:
            zs.append(x)
            return zs, True
    return [], False


def main():
    n, s = [int(x) for x in input().split()][:2]
    xs = [int(x) for x in input().split()][:n]
    result, r = do(s, xs)
    if r:
        print(' '.join(str(x) for x in sorted(result)))
    else:
        print('no combination')


if __name__ == '__main__':
    main()

같은 리스트에서 목표를 28로 하였을때 3, 25만 나오네요 (3, 6, 19) (9, 19)는 누락됐어요 - 디디, 2016/10/27 10:47 M D
+1 네, 암꺼나 빨리 맞추고 다른 놀이기구 타러가야 하기 때문에.... - 룰루랄라, 2016/10/27 10:58 M D
최고입니다^^ - 디디, 2016/10/27 11:22 M D
친절한 설명 감사합니다^^ 그러나 저의 좌절은 아직 끝나지 않았습니다. 하나하나 뜯어서 다시 볼게요^^ - 디디, 2016/10/28 11:53 M D
감사합니다. - Dr.Choi, 2017/01/11 01:13 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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


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