변경이력

돌아가기
2 3287개 문자 추가

2016/10/28 00:22

룰루랄라

(수정) 디디님 너무 좌절하시는 거 같아서.... N개의 숫자에 대해서 임의의 A개의 숫자를 골라 더할 수 있는 경우는 2^N이고, 전체 케이스를 완전 탐색한다고 하면, 지수적 시간복잡도를 갖는 문제이고, 다항 시간 내에 풀기도 쉽지 않을 것 같습니다. 만약 문제에서 "전체 조합을 구하라" 같은 조건이 명시돼 있었다고 가정하면... 만약 입력된 숫자들이 오름차순으로 정렬되어 있다고 할 때 작은 숫자부터 우선 선택하며, 선택한 숫자의 개수도 작도록 숫자를 선별합니다. K 개의 숫자를 골라서 고른 숫자의 합이 S보다 작으면 버리고, 일치하면 줍습니다. 그리고 S보다 크면 K개 조합의 그 이후 버전은 다 볼필요가 없으므로 건너뛸만하겠죠. 이런식으로 볼 필요가 없는 부분들을 빼고 검사해나가면 좀 더 빠르게 풀 수 있습니다만, 숫자의 개수가 아주 많고, 1, 2, 3 등 작은 값들의 비율이 크고 S가 꽤 큰 값이라면 이것 역시 시간이 오래 걸릴 수 밖에 없습니다. ```{python} 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입니다. ```{python} 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() ```
(수정) 디디님 너무 좌절하시는 거 같아서.... N개의 숫자에 대해서 임의의 A개의 숫자를 골라 더할 수 있는 경우는 2^N이고, 전체 케이스를 완전 탐색한다고 하면, 지수적 시간복잡도를 갖는 문제이고, 다항 시간 내에 풀기도 쉽지 않을 것 같습니다. 만약 문제에서 "전체 조합을 구하라" 같은 조건이 명시돼 있었다고 가정하면... 만약 입력된 숫자들이 오름차순으로 정렬되어 있다고 할 때 작은 숫자부터 우선 선택하며, 선택한 숫자의 개수도 작도록 숫자를 선별합니다. K 개의 숫자를 골라서 고른 숫자의 합이 S보다 작으면 버리고, 일치하면 줍습니다. 그리고 S보다 크면 K개 조합의 그 이후 버전은 다 볼필요가 없으므로 건너뛸만하겠죠. 이런식으로 볼 필요가 없는 부분들을 빼고 검사해나가면 좀 더 빠르게 풀 수 있습니다만, 숫자의 개수가 아주 많고, 1, 2, 3 등 작은 값들의 비율이 크고 S가 꽤 큰 값이라면 이것 역시 시간이 오래 걸릴 수 밖에 없습니다. ```{python} 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입니다. ```{python} 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() ```
1 Original

2016/10/24 09:54

룰루랄라

코딩도장

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