본문 바로가기

Algorithm 💡/BruteForce19

[백준 17779번] 게리맨더링2 https://www.acmicpc.net/problem/17779import sysfrom collections import dequeinput = sys.stdin.readline# 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다.# 선거구는 구역을 적어도 하나 포함해야 하고, # 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. # 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다# 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.# 구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값# 선거구를 나누.. 2024. 10. 28.
[소프티어 6273번] 택배 마스터 광우 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai import sysfrom itertools import permutationsinput = sys.stdin.readline# 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 함# N개의 레일, 각 레일은 Ni 무게 전용 레일로 주어진다.(같은 무게의 레일 X)# 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 함# 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐줌# (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛸 순 없다)# 총 k번 일을 하는데 최소한의 무게로 일을 할 수 있도록 하자n, m, k .. 2024. 6. 27.
[소프티어 7594번] 나무 조경 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.aiimport sysfrom itertools import combinationsinput = sys.stdin.readline# 최대 4번 인접해 있는 두 나무를 묶을 예정# 묶은 나무끼리는 서로 겹쳐서는 안됨# 두 나무가 묶였을 때 얻을 수 있는 아름다움은 '두 나무의 키의 합'과 동일# 묶인 쌍의 아름다움의 합을 최대로 만들려고 함n = int(input())heights = [list(map(int,input().split())) for _ in range(n)]dx, dy = [-1,1,0,0], [0,0,-1,1]answer = float("-inf")datas = []for i in range(n): for j in ra.. 2024. 6. 25.
[백준 17471번] 게리맨더링 17471번: 게리맨더링선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.www.acmicpc.netimport sys from itertools import combinations from collections import deque # 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. # 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. input = sys.stdin.readline n = int(input()) peoples = [0] + list(map(int,input().split.. 2024. 4. 8.
[백준 1759번] 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net import copy l, c = map(int,input().split()) alpha_set = set(input().split()) answer = [] vowels = set(['a','e','i','o','u']) # 암호는 서로 다른 L개의 알파벳 소문자들로 구성 # 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성 # 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것 def dfs(string,remain_set):.. 2024. 1. 15.
[백준 2529번] 부등호 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net import copy k = int(input()) signs = list(input().split()) minimum, maximum = float("inf"), float("-inf") def dfs(numbers,num_set): global minimum, maximum, minimum_string, maximum_string length = len(numbers) if length == k+1: # 숫자의 개수가 k+1를 만족할 경우 함수 종료 final_value.. 2024. 1. 15.

티스토리툴바