haejun IT

문제 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 될까? 각 단위의 동전은 무한정 쓸 수 있다. n: 동전의 종류 갯수 m: 거슬러 줄 금액 출력: 거슬러 줄 동전의 최소 갯수를 출력 soltuion n = int(input()) # 동전 종류 갯수 coins = list(map(int, input().split())) coins.sort(reverse=True) # 큰 숫자부터 탐색을 해야 가장 최소 탐색 가능 m = int(input()) # 거슬러줘야할 금액 ret = 2147000000 def recursive(level, sum): global ret if level > ret: # 예를들어, 레벨3 수준에서 (5,5,5)로 ret=15 탐..

문제 1~N까지 번호 적힌 구슬 중복을 허락하여 M번 뽑아 일렬로 나열하는 방법을 모두 출력 my_solution from itertools import product n, m = map(int, input().split()) lists = [i for i in range(1, n + 1)] cnt = 0 for i in product(lists, repeat=m): print(*i, sep=" ") cnt += 1 print(cnt) 중복을 허락하여 모든 조합을 나열해야하기에 product 사용 soltuion n, m = map(int, input().split()) res = [0] * m cnt = 0 def recursive(level): global cnt if level == m: for j..

문제 포인트 트럭에 바둑이를 태우는데, 트럭은 C 킬로그램 넘게 태울 수 없다. C를 넘지 않으면서 바둑이를 가장 무겁게 태우고 싶다. 트럭에 태울 수 있는 가장 무거운 무게를 출력하라 N: 바둑이 마릿수, W: 각 바둑이의 무게 생각 포인트 경우의 수를 따지며, 문제에서 요구하는 최적의 해를 구해야하는 문제 따라서 DFS를 사용하여 풀겠다. my_solution def recursive(level, sum): global largest if sum > c: return if level == n: if sum > largest: largest = sum else: recursive(level + 1, sum + weights[level]) recursive(level + 1, sum) print(larg..

문제 포인트 자연수 n과 n개의 원소로 구성된 자연수 집합이 주어짐 자연수 집합을 두개의 부분집합으로 나누었을 때, 두 부분집합의 합이 서로 같은 경우가 존재하면 'YES'출력, 그렇지 않으면 'NO' 출력 둘로 나뉘는 두 부분집합은 서로소 집합 두 부분집합을 합했을 때, 주어진 원래의 집합이 되어야 한다. e.g) {1, 3, 5, 6, 7, 10} -> {1, 3, 5, 7} = {6, 10} 이므로 'YES' 출력 n = int(input()) nums = list(map(int, input().split())) total = sum(nums) def recursive(level, sum): if sum > (total // 2): # 시간 복잡도 줄이기...