def solution(matrix_sizes):
n = len(matrix_sizes)
d = matrix_sizes[0] + [x[1] for x in matrix_sizes[1:]]
dp = [[0]*n for _ in range(n)]
for gap in range(1, n) :
for i in range(n-gap) :
for k in range(i, (j := i+gap)) :
l = dp[i][k] + dp[k+1][j] + d[i]*d[k+1]*d[j+1]
dp[i][j] = min(dp[i][j], l) if dp[i][j] else l
return dp[0][-1]
두 문제를 합쳐놓은 문제다. 대충설명 할꺼니까 위에 두 문제 모르면 공부ㄱ
import math
def solution(distance, rocks, n):
rocks.sort()
min_, max_ = 1, distance
while min_ < max_ :
destroy = 0; piv_rock = 0
estimate_min_distance = (min_+max_) // 2
for rock in rocks :
if rock - piv_rock < estimate_min_distance : destroy += 1
else : piv_rock = rock
if destroy > n : max_ = estimate_min_distance
else : min_ = estimate_min_distance + 1
return min_ - 1
def solution(n):
if n%2 != 0 : return 0
n_2 = 3
n_1 = 11
for i in range(3, n//2+1) :
n_1, n_2 = (4*n_1 - n_2) % 1000000007, n_1
return n_1
탈인간 코드. 어떻게 이런 패턴을 발견한건지 경이로워서 가져와봄. 이거패턴 무슨 방식인지 좀 알려주셈 난 도저히 모르겠음
def solution(n):
pa, pb, pc, a, b, c = 1, 0, 0, 0, 0, 2
for _ in range(1, n):
pa, pb, pc, a, b, c = a, b, c, (c + pa) % 1000000007, c, (b + a * 2) % 1000000007
return a
from collections import defaultdict
from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
def C(n,k): return comb(n,k)
def solution(a):
one_cnt = [sum(ones) for ones in zip(*a)] # 각열 1의 갯수
DP = defaultdict(int,{(rows := len(a))-one_cnt[0]:comb(rows, one_cnt[0])}) # 1열까지 계산한 DP
for ones in one_cnt[1:]: # DP[2][j] 부터 계산
next_DP = defaultdict(int)
for even_rows in DP:
odd_rows = rows-even_rows
for add_one in range(max(0,ones-odd_rows), min(ones,even_rows)+1): # range 범위는 미만이기때문에 +1
next_DP[even_rows+ones-2*add_one] += DP[even_rows] * C(even_rows, add_one) * C(odd_rows, ones-add_one)%(10**7+19)
DP = next_DP
return DP[rows]
import heapq
def solution(land, height):
N = len(land)
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
board = [[0]*N for _ in range(N)]
que = [(0, 0, 0)]
answer = 0
while que :
cost, h, w = heapq.heappop(que)
if board[h][w] : continue
board[h][w] = 1
answer += cost
cur_height = land[h][w]
for next_h, next_w in [[h+dh, w+dw] for dh, dw in d if 0 <= h+dh < N and 0 <= w+dw < N] :
next_height = land[next_h][next_w]
next_cost = n_cost if (n_cost := abs(cur_height - next_height)) > height else 0
heapq.heappush(que, (next_cost, next_h, next_w))
return answer
def solution(A, B):
A.sort()
B.sort()
a = b = 0
for _ in range(len(A)) :
if A[a] < B[b] :
a += 1
b += 1
return a
A 의 원소 a 보다 큰 B의 원소 중 b 의 최소값들의 갯수를 구하는 문제다.
a보다 큰b들 중 최소값의 갯수
from collections import defaultdict
to_minute = lambda time : sum([int(x)*y for x, y in zip(time.split(':'), [60, 1])])
to_time = lambda minute : ':'.join(map('{0:02d}'.format, divmod(minute, 60)))
def solution(n, t, m, timetable):
minute_table = sorted(map(to_minute, timetable))
bus_table = {to_minute('09:00')+t*i:[] for i in range(n)}
for bus in bus_table :
for j in range(m) :
if minute_table and minute_table[0] <= bus :
bus_table[bus].append(minute_table.pop(0))
last_time, last_bus = list(bus_table.items())[-1]
return to_time(last_time) if len(last_bus) < m else to_time(max(last_bus)-1)
from collections import defaultdict
import re
from decimal import Decimal
def solution(word, pages) :
word = word.lower()
web = defaultdict(defaultdict)
link_score = defaultdict(int)
url_pattern = re.compile('<meta property=\"og:url\" content=\"(.+?)"')
body_pattern = re.compile(r'\<body>\n(.+?)\n\</body>', re.S)
ext_url_pattern = re.compile('<a href="(.+?)"')
for index, page in enumerate(pages) :
page = page.lower()
url = url_pattern.findall(page).pop()
web[url]['index'] = index
body = ' '.join(body_pattern.findall(page))
web[url]['ext_url'] = ext_url_pattern.findall(body)
web[url]['basic_score'] = Decimal(str(re.sub('[^a-z]', '.', body).split('.').count(word)))
for ext_url in web[url]['ext_url'] :
link_score[ext_url] += web[url]['basic_score'] / len(web[url]['ext_url'])
return sorted([[val['basic_score'] + link_score[url], val['index']] for url, val in web.items()], key = lambda x : (-x[0], x[1]))[0][1]
import sys
sys.setrecursionlimit(10**6)
class Tree:
def __init__(self,dataList):
self.data = max(dataList, key = lambda x :x[1]) # dataList 중 y값이 가장 큰 노드
leftList = list(filter(lambda x :x[0] < self.data[0] , dataList)) # data를 기준으로 왼쪽 트리
rightList = list(filter(lambda x :x[0] > self.data[0] , dataList)) # data를 기준으로 오른쪽 트리
self.left= Tree(leftList) if leftList else None # 왼쪽 트리 재귀
self.right=Tree(rightList) if rightList else None # 오른쪽 트리 재귀
def order(node,postList = [],preList = []):
postList.append(node.data[-1]+1) # postorder index
if node.left is not None:
order(node.left,postList,preList)
if node.right is not None:
order(node.right,postList,preList)
preList.append(node.data[-1]+1) # preorder index
return [postList, preList]
def solution(nodeinfo):
root = Tree([x+[i] for i, x in enumerate(nodeinfo)])
return order(root)
from itertools import product
def solution(N, road, K):
DP = [[500000] * N for _ in range(N)]
road.sort(key = lambda x : x[2], reverse = True)
for v1, v2, cost in road:
DP[v1 - 1][v2 - 1] = DP[v2 - 1][v1 - 1] = cost
for t in range(N):
DP[t][t] = 0
for via, i, j in product(range(N), repeat=3):
if DP[i][j] > (l := DP[i][via] + DP[via][j]):
DP[i][j] = l
return len([x for x in DP[0] if x <= K])