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])
import sys
sys.setrecursionlimit(10**6)
import math
def solution(n, stations, w, begin = 1):
if not stations :
return math.ceil((n-begin+1) / (2*w+1))
station = stations.pop()
if station+w >= n :
return solution(station-w-1, stations, w, begin)
if station-w <= begin :
return solution(n, stations, w, station+w+1)
return solution(station-w-1, stations, w, begin) + solution(n, stations, w, station+w+1)
def queens(n, board, h) :
ans = 0
if h == n :
return 1
for w in range(1, n+1) :
board[h + 1] = w
if promising(board, h+1) :
ans += queens(n, board, h+1)
return ans
def promising(board, h) :
for h_ in range(1, h) :
if (w_ := board[h_]) == (w := board[h]) or h - h_ == abs(w_ - w) :
return False
return True
solution = lambda n : queens(n, [0]*(n+1), 0)
def solution(n, first = 1, second = 2, third = 3):
return solution(n-1, first, third, second) + [[first, third]] + solution(n-1, second, first, third) if n else []