from itertools import accumulate,combinations
def solution(cookie):
acc = set(accumulate([0] + cookie))
answer = [abs(x - y) // 2 for x, y in combinations(acc, 2) if (m := x + y) % 2 == 0 and m // 2 in acc]
return max(answer, default=0)
import sys
sys.setrecursionlimit(10**6)
def solution(k, room_number):
global pointer
pointer = {}
return [check_in(room) for room in room_number]
def check_in(room) :
if room not in pointer :
pointer[room] = room + 1
return room
pointer[room] = (avail := check_in(pointer[room]))
return avail
๋๋์ง ๋ฌธ์ ์ 100% ๋์ผ
def solution(sticker):
if len(sticker) < 3 : return max(sticker) # ์คํฐ์ปค๊ฐฏ์ 3๊ฐ๊ฐ ์๋ ๊ฒฝ์ฐ
x1, y1, z1 = sticker[0], max(sticker[:2]), max(sticker[0]+sticker[2], sticker[1]) #์ฒซ์ง ํฐ๋ ๊ฒฝ์ฐ
x2, y2, z2 = 0, sticker[1], sticker[2] # ์ฒซ์ง ์ํฐ๋ ๊ฒฝ์ฐ
for i in sticker[3:]:
x1, y1, z1 = y1, z1, max(x1, y1)+i
x2, y2, z2 = y2, z2, max(x2, y2)+i
return max(x1, y1, y2, z2)
from math import comb
solution = lambda n : comb(2 * n, n) / (n + 1)
def divisor(m) :
for i in range(2, int(m**0.5)+1) :
if m%i == 0 and (measure := m//i) <= 10000000 : return measure
return 1 if m > 1 else 0
def solution(begin, end):
return [divisor(x) for x in range(begin, end+1)]
def solution(n, cores):
min_ = min(cores) * (n//len(cores))
max_ = max(cores)* (n//len(cores))
while min_ < max_ :
t = (min_+max_)//2
cnt_jobs = sum(t//core + 1 for core in cores)
if cnt_jobs >= n :
max_ = t
else :
min_ = t + 1
free_cores_at_t = [i for i, core in enumerate(cores) if min_ % core == 0]
left_jobs_at_t = n - sum((min_-1)//core + 1 for core in cores)
return free_cores_at_t[left_jobs_at_t - 1] + 1
๊ธฐ๋ณธ์ ์ธ BFS ๋ฌธ์ .
import numpy as np
def solution(maps):
board = np.pad(maps, ((1,1),(1,1)), 'constant', constant_values=0).tolist() # 1์นธ์ฉ ํจ๋ฉ
n, m = len(board)-2, len(board[0])-2 # ์๋ณธ ๋งต ํฌ๊ธฐ
d = [(0, 1), (1, 0), (0, -1), (-1, 0)] # ์ด๋ ๋ฒกํฐ
que = [[1, 1, 1]] # h, w, cost
while que :
h, w, cost = que.pop(0)
if cost > n*m : continue # ๋ชฉํ์ง์ ๊น์ง ๋ชป๊ฐ๋ ๊ฒฝ์ฐ
if (h, w) == (n, m) : return cost # ๋ชฉํ์ง์ ๋๋ฌ ํ์ ๊ฒฝ์ฐ
for next_h, next_w in [[h+dh, w+dw] for dh, dw in d] :
if board[next_h][next_w] != 0 : # ๋ฒฝ์ด ์๋ ๊ฒฝ์ฐ
que.append([next_h, next_w, cost+1])
board[next_h][next_w] = 0 # ์ด๋ฏธ ์ง๋๊ฐ ๊ธธ์ ๋ฒฝ์ผ๋ก ๋ง์
return -1
์ต์ ํ๋ ฌ๊ณฑ์ ์ ๊ทธ๋ ์ด๋ ๋ฌธ์ . ํ์ง๋ง 2๊ฐ์ง ํ์ด๊ฐ ์กด์ฌํ๋ค.
import re
def solution(arr):
num = re.findall('\d+', (k := ''.join(arr)))
sign = re.findall('\D', k )
n = len(num)
dp_max = [[-1e9]*n for _ in range(n)]
dp_min = [[1e9]*n for _ in range(n)]
for i in range(n) :
dp_max[i][i] = int(num[i])
dp_min[i][i] = int(num[i])
for gap in range(1, n) :
for i in range(n-gap) :
for k in range(i, (j := i+gap)) :
if sign[k] == '+' :
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k+1][j])
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k+1][j])
else :
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] - dp_min[k+1][j])
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] - dp_max[k+1][j])
return dp_max[0][-1]
from collections import defaultdict
def solution(sales, links):
global graph, DP
graph = defaultdict(list)
for v1, v2 in links :
graph[v1-1].append(v2-1)
DP = [[0, 0, 0] for _ in range(len(sales))]
dfs(sales, 0)
return min(DP[0][0], DP[0][1])
def dfs(sales, node) :
if node not in graph :
DP[node][1] = sales[node]
else :
for child in graph[node] :
dfs(sales, child)
children = graph[node]
flag = sum(DP[child][2] for child in children)
DP[node][1] = sales[node] + (s := sum(min(DP[child][0] , DP[child][1]) for child in children))
DP[node][0] = s if flag else s + min(DP[child][1] - DP[child][0] for child in children)
DP[node][2] = 1 if DP[node][1] < DP[node][0] else 0
from collections import defaultdict, deque
from copy import deepcopy
def level(node, levels) :
levels[node] = -1
que = deepcopy(graph[node])
level = 0
while que :
for _ in range(len(que)) :
child = que.popleft()
if not levels[child] :
levels[child] = level + 1
que.extend(deepcopy(graph[child]))
level += 1
return levels
def solution(n, edges):
global graph
graph = defaultdict(deque)
for v1, v2 in edges:
graph[v1-1].append(v2-1)
graph[v2-1].append(v1-1)
v1 = level(0, [0]*n)
v2 = level(v1.index(max(v1)), [0]*n)
if v2.count((max_ := max(v2))) >= 2 :
return max_
else :
v3 = level(v2.index(max_), [0]*n)
return max_ if v3.count((max_ := max(v3))) >= 2 else max_ - 1