https://www.acmicpc.net/problem/22953코드n, k, c = map(int, input().split())cooking_times = list(map(int, input().split()))INF = int(1e12)answer = INFdef total_cooking_time(arr, k): result = INF l, r = 1, INF while l 해당 문제를 풀기 위해서는 두 가지 알고리즘을 사용해야 했다. - 백트래킹: 가능한 모든 격려 조합을 탐색하며 최적의 해를 찾는 데 사용- 파라메트릭 서치: k개 이상의 요리를 만들 수 있는 최소 시간을 찾는 데 사용 좀 더 자세하게 말해보자면 다음과 같은 과정으로 진행했다.백트래킹각 셰프에게 c번의 격려를 ..
문제풀이/백트래킹
https://school.programmers.co.kr/learn/courses/30/lessons/92343코드function solution(info, edges) { let answer = 0; const n = info.length; const graph = Array.from(new Array(n), () => []); for (const [a, b] of edges) { graph[a].push(b); } const visited = new Array(n).fill(false); const bt = (sheep, wolf) => { answer = Math.max(answer, sheep); for (const [s, e] of edges) { if (..
https://school.programmers.co.kr/learn/courses/30/lessons/64064코드function solution(user_id, banned_id) { let answer = new Set(); const get_pattern = (id) => { const transformed = id.replace(/\*/g, "."); return new RegExp(`^${transformed}$`); }; const check_banned = (pattern) => { return user_id.filter((id) => pattern.test(id)); }; const bt = (idx, banned_set) => { if (idx === b..
https://www.acmicpc.net/problem/14650코드n = int(input())answer = 0def bt(n, chosen): global answer if len(chosen) == n: if sum(chosen) % 3 == 0: answer += 1 return start = 1 if len(chosen) == 0 else 0 for i in range(start, 3): bt(n, chosen+[i])bt(n, [])print(answer) 3의 배수는 각 자릿수의 합이 3의 배수라는 것은 수학적 사실이다. 이러한 수학적 사실과 백트래킹 알고리즘을 사용하여 풀었다. 0,1,2 중 N개의 숫자를 중..
https://www.acmicpc.net/problem/2057코드n = int(input())factorial = [1]for i in range(1, 20): factorial.append(factorial[-1]*i)answer = "NO"def bt(num, total): global answer if total == n: answer = "YES" return elif total > n or num >= 20: return # num을 포함 bt(num+1, total+factorial[num]) # num을 포함X bt(num+1, total)if n != 0: bt(0, 0)print(answer) 문제에..
