khakha's dev log

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근 select_chicken() : 백트래킹으로 주어진 M 갯수만큼의 치킨 조합 구성 calc_dist() : 조합이 완성되면 각 집별로 가까운 치킨 거리를 구해서 도시의 치킨 거리 최솟값을 구해준다. 코드 # 백트래킹 풀이 N,M = map(int, input().split(' ')) city = [] home = [] chick = [] visit = [[0 fo..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근 브루트포스 (백트래킹) 주어진 +,-,*,/ 갯수를 하나씩 빼가면서 dfs 탐색 + 백트래킹을 통해 모든 경우의 수를 탐색한다. 코드 N = int(input()) num = list(map(int, input().split())) add, sub, mul, div = map(int, input().split()) min_value..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 백트래킹 + dfs 벽을 세울 수 있는 자리에 3개 벽을 세우는 모든 경우를 찾고 모든 경우 마다 안전 영역을 dfs를 통해 구한 후, 가장 큰 값을 구해준다. 코드 from collections import deque # import copy import sys input = sys.stdin.readline def bfs(): # copy_area = copy.deepcopy(area) -> 속..