2233번: 사과나무 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리 www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**6) n = int(input()) binary = '9' + input() x, y = map(int, input().split()) parent = [[] for _ in range(n+1)] # 각 노드의 부모(가까운 노드부터) depth = [-1] * (n+1) # 각 노드의 깊이 removed = [] inout = [[] for _ in range(n+1)] de..
전체 글
17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) n, w = map(int, input().split()) edges = [[] for _ in range(n+1)] for _ in range(n-1): u, v = map(int, input().split()) edges[u].append(v) edges[v].append(u) visited = ..
16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 코드 r, c = map(int, input().split()) map_data = [] for i in range(r): map_data.append(list(input())) dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] for i in range(r): for j in range(c): if map_data[i][j] == 'W': for d in range(4): nx = i+dx[d] ny = j+dy[d] if 0
14575번: 뒤풀이 첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109) 둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106) www.acmicpc.net 코드 n, t = map(int, input().split()) alcohol = [list(map(int, input().split())) for _ in range(n)] s, e = 1, int(1e9) ans = int(1e9) while s mid: low = -1 break low += alcohol[i][0] high += min(mid, alcohol[i][1]) if low == -1 or high < t: s = mid..
1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) n = int(input()) v = [0]+[int(input()) for _ in range(n)] dp = [[0]*(n+1) for _ in range(n+1)] def recursion(l, r, cnt): if l > r: return 0 if dp[l][r] != 0: return dp[l][r] dp[l][r] = max(v[l]*cnt+recursion(l+..
1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 코드 n, l, w, h = map(int, input().split()) s, e = 0, max(l, w, h) ans = 0 for _ in range(100): mid = (s+e)/2 boxes = (l//mid)*(w//mid)*(h//mid) if boxes < n: e = mid else: ans = mid s = mid print(ans) 이분탐색의 시간복잡도는 $O(logN)$으로 0~1,000,000,000 범위를 탐색한다면 반복문을 1..