꾸준하게 거북이처럼

def DFS(v): global cnt if v == n: cnt += 1 for k in path: print(k, end= ' ') print() else: for i in range(1,n+1): if ch[i] == 0 and g[v][i] == 1: ch[i] = 1 path.append(i) DFS(i) ch[i] = 0 path.pop() if __name__ == "__main__": n, m = map(int,input().split()) # 1 부터 n 까지 연결 여부, 방문 여부를 위한 배열 g 와 ch g = [[0] * (n + 1) for _ in range(n + 1)] ch = [0] * (n + 1) # 항상 1부터 방문시작을 하므로 1로 체크한다. ch[1] = 1 cn..

import itertools as it n, f = map(int,input().split()) b = [1] * n cnt = 0 for i in range(1,n): b[i] = b[i-1] * (n - i)//i a = list(range(1, n + 1)) for tmp in it.permutations(a): sum = 0 for L, x in enumerate(tmp): sum += (x * b[L]) if sum == f: for x in tmp: print(x, end=' ') break # 파스칼 삼각형의 합으로 수열 추측하기 문제이다. 전과 다르게, 라이브러리를 이용해서 풀면 위와 같다. # 파이썬은 수열을 자동으로 만들어주는 라이브러리를 제공해 주는데, 라이브러리에 너무 의존하면 안..

def DFS(L,s): global cnt, res if L == k: if sum(res) % m == 0: cnt += 1 else: for i in range(s, n): res[L] = arr[i] DFS(L+1,i+1) if __name__ == "__main__": n, k = map(int,input().split()) arr = list(map(int,input().split())) m = int(input()) res = [0] * k cnt = 0 DFS(0,0) print(cnt) # n개의 수에서 k개를 뽑았을 때 그 합이 m의 배수인 경우의 개수를 구하자. # 나의 풀이: 조합구하기에서 해당 조합의 sum이 sum % m == 0 가 되는지 확인만 하면 된다. # 따라서 조합을 ..

def DFS(L): global cnt, res count = 0 for i in res: if i > 0 : count += 1 if count n: return if count == m: for k in range(1,n+1): if res[k] > 0: print(k, end=' ') cnt += 1 print() else: res[L] = 1 DFS(L+1) res[L] = 0 DFS(L+1) if __name__ == "__main__": n, m = map(int,input().split()) res = [0] * (n+1) cnt = 0 DFS(1) print(cnt) # 나의 풀이: 어떻게 문제를 풀지는 부분집합 구하기에서 응용을 하면 된다. 하지만 종료조건을 하나 ..

import sys def pascalSum(res): temp = [] while len(res) != 1: for i in range(len(res)-1): temp.append(res[i] + res[i+1]) res = temp.copy() temp = [] return res[0] def DFS(L): global cnt, res if L == n: result = pascalSum(res) if result == F: for i in res: print(i, end= ' ') sys.exit(0) else: for i in range(1,n+1): if i not in res[:L]: res[L] = i DFS(L+1) if __name__ == "__main__": n, F = map(int..

def DFS(L): global cnt, res if L == m: for i in res: print(i, end= ' ') print() cnt += 1 else: for i in range(1,n+1): if i not in res[:L]: res[L] = i DFS(L+1) if __name__ == "__main__": n, m = map(int,input().split()) res = [0] * m cnt = 0 DFS(0) print(cnt) # 중복순열 구하기에서 중복만 뺀 것으로, 앞에서 선택한 수는 포함하지 않아야한다. # 나의 풀이: L 즉, 현재 레벨 전까지 선택한 수들은 제외하고 선택해야하므로, res[:L] 배열에 속하지 않은 # 수를 선택해서 순열을 만들어 나가는 방식으로 구..

def DFS(L): global res, min if sum(res) > M: return count = 0 for k in res: if k != 0: count += 1 if min count: min = count return else: for i in range(n): res[L] = coins[i] DFS(L+1) if __name__ == "__main__": n = int(input()) coins = list(map(int,input().split())) coins.sort(reverse=True) M = int(input()) res = [0] * M min = 21470000 DFS(0) print(min) ..

import sys input = sys.stdin.readline def DFS(L): global cnt if L == m: for k in range(m): print(res[k], end=' ') print() cnt += 1 else: for i in range(1,n + 1): res[L] = i DFS(L+1) if __name__ == "__main__": n, m = map(int,input().split()) cnt = 0 res = [0] * m DFS(0) print(cnt) # 중복순열이기 때문에 1 ~ n 까지 m개 뽑을 때까지 계속 반복해서 재귀 호출을 해야한다. => for문 n번 반복 # 첫 시작 호출은 루트로 출발하는 것이 항상 확실하다. 여기서는 0을 출발점으로 둔다. ..

def DFS(index, sum): global max if sum > C: return if index == N: if sum > max: max = sum else: DFS(index + 1, sum + arr[index]) DFS(index + 1, sum) if __name__ == "__main__": C, N = map(int,input().split()) arr = [] max = 0 for _ in range(N): arr.append(int(input())) DFS(0,0) print(max) # 나의 풀이 # 바둑이들을 무게 C가 넘지 않게 최대한 무겁게 트럭에 싣자. # DFS를 이용해서 매개변수를 sum으로 전달해서 C를 넘으면 return, max를 전역변수로 두어서 sum이 m..

a = [] def DFS(n): if n > 3: for i in a: print(i, end=' ') print() return else: a.append(n) DFS(n+1) a.pop() DFS(n+1) # ------^나의 풀이 def dfs(v): if v == n + 1: for i in range(1, n + 1): if ch[i] == 1: print(i, end= ' ') print() else: ch[v] = 1 dfs(v + 1) ch[v] = 0 dfs(v + 1) if __name__ == "__main__": n = int(input()) ch = [0] * (n + 1) dfs(1) # ------^정답 풀이 # 원소가 1 2 3인 집합의 부분집합 구하기. # 나의 풀이 : ..