https://www.acmicpc.net/problem/7490 코드ans = []def bt(n, idx, exp): if idx == n: exp += str(idx) if eval(exp.replace(" ", '')) == 0: ans.append(exp) return for mid in ['+', '-', ' ']: bt(n, idx+1, exp+str(idx)+mid)for _ in range(int(input())): n = int(input()) ans = [] # 정답 배열 초기화 bt(n, 1, "") ans.sort() # ASCII 순서로 정렬 for i in rang..
backtracking
https://www.acmicpc.net/problem/15270 코드n, m = map(int, input().split())friends = []for _ in range(m): u, v = map(int, input().split()) friends.append((u, v))ans = 0def bt(used, idx): global ans if idx == m: if len(used) 입력으로 받은 친한 친구 관계 friends에서 각 원소의 커플을 넣는다/넣지 않는다 2가지 경우로 나눠서 탐색하면 된다. 예를 들어서 친한 친구 관계 (1, 2)가 있다고 할 때 1과 2가 같이 춤을 출 지, 안 출 지로 나누는 것이다.만약 같이 출 것이라면 이 커플의 2명 다 ..
https://www.acmicpc.net/problem/2661 코드n = int(input())def chk(seq): l = len(seq) for i in range(2, len(seq)//2+1): if seq[l-i:] == seq[l-i*2:l-i]: return False return Truedef bt(seq): if len(seq) == n: print(seq) exit() for i in range(1, 4): if seq != '' and str(i) == seq[-1]: # 1글자 부분 수열 확인 continue if chk(seq+str(i)): #..
https://www.acmicpc.net/problem/1469 코드from copy import deepcopyn = int(input())x = sorted(list(map(int, input().split())))answer = []arr = [-1]*(2*n)def bt(idx): if idx == n: new_arr = deepcopy(arr) answer.append(new_arr) return for i in range(2*n-x[idx]-1): if arr[i] == -1 and arr[i+x[idx]+1] == -1: arr[i] = x[idx] arr[i+x[idx]+1] = x[idx..
10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 코드 arr = input() # 최대 수 N 구하기 if len(arr) < 10: max_num = len(arr) else: max_num = (len(arr)-9)//2+9 def find_seq(arr, seq): if len(arr) == 0: # 1~N까지의 수로 이루어진 순열인지 확인 sorted_seq = sorted(seq) possible = True for i in range(1, len(sorted_seq)): if so..
