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
def solution(play, adv, logs):
to_seconds = lambda time_: sum([int(x)*y for x, y in zip(time_.split(':'), [3600, 60, 1])])
split = lambda times_ : times_.split('-')
play, adv = to_seconds(play), to_seconds(adv)
logs = sorted([s for start, end in map(split, logs) for s in [(to_seconds(start), 1), (to_seconds(end), -1)]])
viewers, cur_time, viewers_list = 0, 0, [0] * play
for log, state in logs:
if viewers > 0:
viewers_list[cur_time:log] = [viewers] * (log - cur_time)
viewers, cur_time = viewers + state, log
adv_filter, adv_start_time = (s := sum(viewers_list[:adv]), 0)
for i, j in zip(range(play - adv), range(adv, play)):
s += viewers_list[j] - viewers_list[i]
if s > adv_filter:
adv_filter, adv_start_time = s, i + 1
return f"{adv_start_time//3600:02d}:{adv_start_time%3600//60:02d}:{adv_start_time%60:02d}"
code by ์ค์๊ตฌ
from itertools import product
def solution(n, s, a, b, fares):
s, a, b = s - 1, a - 1, b - 1
DP = [[100000000] * n for _ in range(n)]
for v1, v2, cost in fares:
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 min(DP[s][k] + DP[k][a] + DP[k][b] for k in range(n))
๋ ํญ์ ๋ฌธ์ ํ๊ณ ๋ค๋ฅธ์ฌ๋๋ค์ ํ์ด ๋๋ต 3ํ์ด์ง๊น์ง ํ์ด๋ณด๋๋ฐ, ์ค์๊ตฌ ์ด์ฌ๋ ์ฝ๋ฉ์คํ์ผ์ด ๋๋ ๋น์ทํ๋ฐ ์ค๋ ฅ์ด ๋ ์ข๋ค. ๋ฑ ๋ณด๊ณ ์ค ์ข์น๋ค? ํ๊ณ ์ด๋ฆ๋ณด๋ฉด ์ค์๊ตฌ ์ด์ฌ๋์ธ ๊ฒฝ์ฐ๊ฐ ๊ฝค ๋ง์๋ค. ์ด๊ฒ๋ ์ด์ฌ๋ ์ฝ๋์
๋๋ฌด ์์งฐ๊ธธ๋ ๊ฐ์ ธ์ด
from collections import defaultdict
def solution(n, results):
answer = 0
win, lose = defaultdict(set), defaultdict(set)
for winner, loser in results:
lose[loser].add(winner)
win[winner].add(loser)
for i in range(1, n + 1):
for winner in lose[i]: win[winner] |= win[i]
for loser in win[i]: lose[loser] |= lose[i]
for i in range(1, n+1):
if len(win[i]) + len(lose[i]) == n - 1: answer += 1
return answer
from collections import defaultdict
def solution(genres, plays):
dic = defaultdict(list)
for i, info in enumerate(zip(genres, plays)) :
kind, play_time = info
dic[kind].append([i, play_time])
answer = []
for k in sorted(dic.values(), key = lambda info : sum(play_time for i, play_time in info), reverse = True) :
answer.extend(sorted(k, key = lambda info : info[1], reverse = True)[:2])
return [index for index, _ in answer]
import numpy as np
def solution(m, n, puddles):
board = [[0 for _ in range(m+1)] for _ in range(n+1)]
board[0][0]=1
for h in range(n) :
for w in range(m) :
if [w+1, h+1] in puddles: continue # ํ์ฌ ์์น๊ฐ ๋ฌผ์
๋ฉ์ด๋ผ๋ฉด continue
board[h][w+1] += board[h][w]
board[h+1][w] += board[h][w]
return board[n-1][m-1] % 1000000007
def solution(s):
for end in range(len(s), 0, -1):
for start in range(0, len(s)-end+1):
substr = s[start:start+end]
if substr == substr[::-1]:
return len(substr)
import numpy as np
def solution(n, times):
times = np.array(sorted(times))
min_ = times[0] * (n//len(times))
max_ = times[-1]* (n//len(times))
while min_ < max_ :
estimate = (min_+max_) // 2
total_p = (estimate//times).sum()
if total_p < n :
min_ = estimate+1
else :
max_ = estimate
return int(min_)