def solution(n, s):
num, res = divmod(s, n)
if n > s :
return [-1]
answer = [num for _ in range(n)]
for i in range(res) :
answer[-1-i] += 1
return answer
입국심사와 매우 비슷한 문제다. 혹시 이문제를 모른다면 무조건 보고와야한다.
def check(stones, k, people) :
sinked = 0
for stone in stones :
sinked = sinked + 1 if stone < people else 0
if sinked == k : return False
return True
def solution(stones, k):
min_ = min(stones)
max_ = max(stones)
if min_ == max_ : return min_
while min_ < max_:
estimate = (min_ + max_) // 2
if check(stones, k, estimate) :
min_ = estimate + 1
else:
max_ = estimate
return min_ - 1
from math import factorial
solution = lambda n, k : recur([x for x in range(1, n+1)], k-1)
def recur(nums, k) :
if (n := len(nums)) == 1 :
return [nums.pop()]
index, rest = divmod(k, factorial(n-1))
return [nums.pop(index)] + recur(nums, rest)
from collections import Counter
def solution(a):
elements = Counter(a).most_common()
answer = 0
for k, v in elements:
if v <= answer : break
star = 0
idx = 0
while idx < len(a)-1:
if k not in a[idx:idx+2] or (a[idx] == a[idx+1]):
idx += 1
continue
star += 1
idx += 2
answer = max(star, answer)
return answer * 2
import bisect
def solution(n, works):
works.sort()
for _ in range(n) :
max_num = works.pop(-1)
if max_num < 1 :
return 0
bisect.insort_left(works, max_num-1)
return sum(x**2 for x in works)
import re
from itertools import permutations
def check(banned_permutations, patterns) :
for pattern, ban_id in zip(patterns, banned_permutations) :
if not pattern.fullmatch(ban_id) :
return False
return True
def solution(user_id, banned_id):
answer = []
patterns = [re.compile(x.replace('*', '.')) for x in banned_id]
for banned_permutations in permutations(user_id, len(banned_id)):
if check(banned_permutations, patterns) and set(banned_permutations) not in answer:
answer.append(set(banned_permutations))
return len(answer)
Lv.5 방의갯수문제와 90% 이상 비슷한 문제다.
from collections import defaultdict
add = lambda x, y : (x[0]+y[0], x[1]+y[1])
check = lambda point, next_point, dir_ : (move[dir_][2] not in points[next_point]) and (dir_ not in points[point])
def solution(dirs):
global points, move
answer = 0
move = {'U':(-1, 0, 'D'), 'R':(0, 1, 'L'), 'D':(1, 0, 'U'), 'L':(0, -1,'R')}
points = defaultdict(set)
point = (0, 0)
for dir_ in dirs :
next_point = add(point, move[dir_])
if not(-5<=next_point[0]<=5 and -5<=next_point[1]<=5) :
continue
answer += 1 if check(point, next_point, dir_) else 0
points[point].add(dir_)
point = next_point
return answer
from functools import reduce
def solution(n):
return reduce(lambda x, n :[x[1], x[0] + x[1]], range(n), [0, 1])[-1] % 1234567
def solution(n, money):
money.sort()
dp = [0]*(n+1)
for m in money :
dp[m] += 1
for index in range(m+1, len(dp)) :
dp[index] += dp[index-m]
return dp[-1]
from itertools import permutations
from collections import defaultdict
import copy
def solution(board, r, c):
global graph_, board_
answer = 1e9
graph = defaultdict(list)
for h in range(4) :
for w in range(4) :
if board[h][w] != 0 :
graph[board[h][w]].append([h, w])
for order in permutations(graph) :
que = [[r, c, 0]]
board_ = copy.deepcopy(board)
for v in order :
p1, p2 = graph[v]
for i in range(len(que)) :
h, w, cost = que.pop(0)
que.append(p1 + [cost + navigation([h, w], p2) + navigation(p2, p1)])
que.append(p2 + [cost + navigation([h, w], p1) + navigation(p1, p2)])
board_[p1[0]][p1[1]] = 0
board_[p2[0]][p2[1]] = 0
que.sort(key = lambda x : x[2])
answer = min(answer, que[0][2])
return answer + len(graph)*2
def navigation(p1, p2) :
h1, w1 = p1
h2, w2 = p2
return min(straight(board_[h1], w1, w2) + straight([x[w2] for x in board_], h1, h2), \
straight(board_[h2], w1, w2) + straight([x[w1] for x in board_], h1, h2))
def straight(list_, x, y) :
result = abs(x-y)
zeros = len([x for x in list_[min(x, y)+1:max(x, y)] if x == 0])
if result == 2 and list_[y] == 0 and 0<y<3 :
return result
return result - zeros