모눈종이에 사각사각

🍎 [백준 15686] 치킨 배달 문제 링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net ⚾ 코드 from itertools import combinations n, m = map(int, input().split()) grid = [list(map(int, input().split())) for _ in range(n)] chickens = [] homes = [] for i in range(n): for j in r..

🍎 [백준 1719] 택배 문제링크 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net ⚾ 코드 - 다익스트라 import sys import heapq input = sys.stdin.readline INF = int(1e9) N, M = map(int, input().split()) result = [[0]*(N+1) for _ in range(N+1)] # 결과 테이블 graph = [[] for _ in range(N+1)] for _ in rang..

🍎 [백준 9466] 텀 프로젝트 문제 링크 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ⚾ 코드 import sys sys.setrecursionlimit(1000001) # 재귀 깊이 설정 input = sys.stdin.readline def find_group(start): global group visited[start] = True cycle.append(start) # cycle 리스트에 삽입 if visited[student[sta..

🍎 [백준 13549] 숨바꼭질3 문제링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⚾ 코드 from collections import deque N, K = map(int, input().split()) # N: 언니, K:동생 INF = int(1e9) second = [INF]*(max(N, K)*2) # 언니와 동생중 큰 값의 두 배 길이의 second 리스트 생성 def check_range(n..

🍎 [백준 11265] 끝나지 않는 파티 문제링크 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net ⚾ 코드 # 11265 끝나지 않는 파티 import sys input = sys.stdin.readline N, M = map(int, input().split()) # N: 파티장의 크기, M: 서비스를 요청한 손님의 수 graph = [list(map(int, input().split())) for _ in..

🍎 [백준 18405] 경쟁적 전염 문제링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net ⚾ 코드 from collections import deque N, K = map(int, input().split()) graph = [[0]*(N+1)] # 1부터 시작하게 하기 위해서 virus_location = [] for i in range(1, N+1): graph.append([0]+list(map(int, ..

🍎 [백준 1707] 이분 그래프 문제링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ⚾ 코드 (PyPy3 제출) from collections import deque K = int(input()) def bfs(graph, i): q = deque() q.append(i) while q: now = q.popleft() for node in graph[now]: if visited[node] == visited[now]: return F..

🍎 [백준 1697] 숨바꼭질 문제링크 https://www.acmicpc.net/problem/1697 ⚾ 코드 from collections import deque N, K = map(int, input().split()) visited = [False for _ in range(200001)] # visited = False or True dx = [1, -1, 2] # move result = 0 q = deque() # start visited[N] = True q.append([N, 0]) while q: x, count = q.popleft() if x == K: # if subin and her sister equal, break result = count break for i in ran..

🍎 [백준 1654] 랜선 자르기 문제링크 https://www.acmicpc.net/problem/1654 이전에 풀었던 2805번 나무 자르기 문제와 굉장히 유사한 문제였다. ⚾ 코드 import sys k, n = map(int, input().split()) array = [int(sys.stdin.readline()) for _ in range(k)] start = 1 end = max(array) while start

🍎 [백준 2805] 나무 자르기 문제링크 https://www.acmicpc.net/problem/2805 ⚾ 코드(pypy3) import sys input = sys.stdin.readline n, m = map(int, input().split()) tree = list(map(int, input().split())) end = max(tree) start = 0 while start mid: remain += i-mid if remain < m: end = mid-1 else: start = mid+1 print(end) 🔔 해결 과정 & 깨달은 점 - 해당 문제는 전형적인 이진탐색 문제이다. - 입력 값이 20억이므로 이진 탐색을 시도해보자. - 처음에 cm가 아닌, 인덱스의 중앙값으로 시도를..