코테 여름방학 챌린지 2주차 - 백트래킹, 재귀함수

N과 M- 백트래킹

# 내풀이 -> permutation 라이브러리 씀 
import sys 
input = sys.stdin.readline 

#N, M 
N, M = map(int, input().split())
from itertools import permutations 

lst = [i for i in range(1, N+1)]
#print(lst)
for per in permutations(lst, M): 
	#print(per)#출력을 그냥 
	for p in per: 
		print(p, end = " ")
	print()

1182. 부분수열의합

1. 조합으로 해서 합이 M이 되는 개수 구하는 방법 -> 내 풀이

import sys 
input = sys.stdin.readline
N, M = map(int, input().split())
lst = [int(i) for i in input().split()]
print(lst)

from itertools import combinations
count = 0
for i in range(1, N+1): 
	for comb in combinations(lst, i): 
		if sum(comb) == M: 
			count+= 1
print(count)

2. 백트래킹, dfs로 선택 o,x 로 하기
   재귀함수로 해당 원소를 선택하는지, 안하는지를 구현한다.

import sys 
input = sys.stdin.readline
N, M = map(int, input().split())
lst = [int(i) for i in input().split()]

count =0 
def dfs(level, total): 
	global count 
    #종료 조건 
    if level ==N: 
    	if total == M: 
        	count += 1 #개수 세주기 
        return 
    #해당 원소 선택 한다 안한다 
    dfs(level+1, total + lst[level]) 
    dfs(level+1, total) 
dfs(0,0) 

#공집합 제외 
if M ==0: 
	count -= 1 
print(count)
          

18429. 근손실: 조건 찾기 / 백트래킹

import sys 
input = sys.stdin.readline 

#입력 받기 
N, k = map(int, input().split()) 
lst = list(map(int, input().split()))
print(lst)

visited = [0] * N 
count = 0 

def dfs(level, current): 
	global count 
    if current < 500: 
    	return 
    if level == N: 
    	count += 1
       	return
    current -=k 
    
    for i in range(N): 
    	if not visited[i]: 
        	visited[i] =1 
            dfs(level+1, current + lst[i] ) 
            visited[i] = 0 
dfs(0,500)
print(count)

11729. 하노이탑 / 재귀

#N개 입력받기 
#하노이 함수 정의 
N = int(input())

#원판이 하나: 1-> 3
#N이 2개이상이면 
#시작 기둥 -> 보조기둥 
def hanoi(n, start, mid, end): 
	#원판이 1개일때 
	if n ==1: 
		print(start, end)
	#2이상일때 3단계 따름 
	#n-1개 start-> mid로 옮김 
	else: 
		hanoi(n-1, start, end, mid)
		#마지막 1개 
		print(start, end) # 마지막 한개는 start-> end로 옮김 
		hanoi(n-1, mid, start, end)

print(2**N -1)
hanoi(N, 1,2,3)

15686. 치킨 집 / 조건, 조합, 2차원

import sys 
input = sys.stdin.readline 

N, M = map(int, input().split())
lst  = [list(map(int, input().split())) for _ in range(N)]

#집, 치킨 집 좌표 리스트 저장 
house = [] 
chicken = [] 

for i in range(N): 
	for j in range(N): 
		if lst[i][j] ==1: 
			house.append((i, j))

		elif lst[i][j] ==2: 
			chicken.append((i,j))

#최소 거리 합을 저장할 변수 
result = float("inf")
print(house, chicken)
#치킨집 Mr개 선택할 조합 
from itertools import combinations
#치킨 집 선택 
for comb in combinations(chicken, M): 
	#현재 조합에 대한 거리 합 
	total = 0 #도시와 치킨 거리 
	#print(comb)
	for x, y  in house: 
		chi_len = float("inf")# 각 집마다 치킨 거리 
		for cx, cy in comb: 
			#print(cx,cy)
			chi_len = min(chi_len, abs(x-cx) + abs(y-cy)) 
			#print(min_dist)
		total+= chi_len 
		#print(total)
	result = min(result, total)
print(result)