백트래킹

[DP] BOJ 2240 자두나무

https://www.acmicpc.net/problem/2240 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import sys from itertools import combinations input = sys.stdin.readline T, W = map(int, input().split()) tree = [0] + [int(input())-1 for t in range(T)] dp = [[0] * (W + 1) for _ in range(T + 1)] # W * T의 배열 for i in range(1, T+1): # 전혀 움직이지 않았을 경우 초기화 if tree[i] == 0: dp[i][0] = dp[i-1][0] + 1 e..

[백트래킹, 시뮬레이션] BOJ 12100 2048(easy)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 import sys import copy input = sys.stdin.readline N = int(input()) board = [list(map(int, input().split())) for _ in ra..

[백트래킹] BOJ 15663 N과 M (9)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = sorted(list(map(int, input().split()))) results = [] def backtracking(n, result): if n == M: print(' '.join(list(map(str, result)))) return duplicate = 0 # 동일한 값일 경우, 조합할 필요가 없음 for i in range(N): if not is_used[i] and duplicate != arr[i] : is_used[i] = True du..

[백트래킹] BOJ 15657 N과 M (8)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys import copy input = sys.stdin.readline def backtracking(n, N, M): if n == M: results.append(copy.deepcopy(sequence)) return for i in range(N): sequence[n] = arr[i] if (n > 0 and sequence[n] >= sequence[n-1]) or n == 0: backtracking(n+1, N, M) N, M = map(int, input().split()) arr = sorted(list(map(int, input().split()))) sequence = ..

[백트래킹] BOJ 15655 N과 M (6)

import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) is_used = [False] * len(arr) arr.sort() def backtracking(n, idx, result): if n == M: print(' '.join(map(str, result))) return for i in range(idx, N): if not is_used[i]: is_used[i] = True new_result = result + [arr[i]] backtracking(n+1, i+1, new_result) is_used[i] = False backtracking(0, 0..

[백트래킹] BOJ 15654 N과 M (5)

import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) is_used = [False] * len(arr) arr.sort() def backtracking(n, idx, result): if n == M: print(' '.join(map(str, result))) return for i in range(N): if not is_used[i]: is_used[i] = True new_result = result + [arr[i]] backtracking(n+1, i+1, new_result) is_used[i] = False backtracking(0, 0, [])..

[백트래킹] BOJ 6603 로또

import sys input = sys.stdin.readline def backtracking(n, idx): if n == 6: result = '' for i in range(len(arr)): if visited[i]: result += str(arr[i]) result += ' ' print(result) return for i in range(idx, N): if not visited[i]: visited[i] = True backtracking(n+1, i+1) visited[i] = False while(1): arr = list(map(int, input().split())) if 0 == arr[0]: break arr = arr[1:] N = len(arr) visited = [Fa..

[백트래킹] BOJ 1759 암호만들기

import sysinput = sys.stdin.readline L, C = map(int, input().split())data = list(map(str, input().split()))visited = [False] * len(data) data.sort()def backtracking(n, idx): if n == L: is_vowel = 0 result = '' for i in range(C): if visited[i]: result += data[i] if data[i] in {'a', 'e', 'i', 'o', 'u'}: is_vowel += 1 if is_vowel and (len(result) - is_vowel) > 1: print(result) return for i in range..

[백트래킹] BOJ 15686 치킨배달

import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] result = sys.maxsize def backtracking(n, idx): global result if idx > len(chickens): return if n == M: h_dist = [sys.maxsize] * len(houses) for i in range(len(chickens)): if visited[i] == True: for j, (h_x, h_y) in enumerate(houses): new_dist = abs(chickens[i][0] - h_x..

[백트래킹] BOJ 14889 스타트와 링크

import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] visited = [ False for _ in range(N) ] result = sys.maxsize def backtracking(n, idx): global result if n == N//2: a_sum, b_sum = 0, 0 for i in range(N): for j in range(i+1, N): if visited[i] and visited[j]: a_sum += arr[i][j] a_sum += arr[j][i] elif not visited[i] and not visited[j]: b..

[백트래킹] BOJ 14888 연산자 끼워넣기

import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) ops = list(map(int, input().split())) global _max global _min _max, _min = -1e9, 1e9 def backtracking(n, total): # 여기서 n은 숫자 위치 global _max global _min if n == N: if total > _max: _max = total if total 0: ops[i] -= 1 if i == 0: backtracking(n+1, total+arr[n]) elif i == 1: backtracking(n+1, total-arr[n]) ..

[백트래킹] BOJ 1182 부분수열의 합

보호되어 있는 글입니다.