Last active
April 28, 2022 09:51
-
-
Save HenryPaik1/24654a0ada7740233aea33140f4c6297 to your computer and use it in GitHub Desktop.
coding-test-book
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ############################ | |
| # 어른 상어 | |
| # https://www.acmicpc.net/submit/19237/41191333 | |
| ############################ | |
| N, M, k = map(int, input().split()) | |
| grid = [list(map(int, input().split())) for _ in range(N)] | |
| direction = [None] + list(map(int, input().split())) | |
| shark_dir = [[], ] | |
| for _ in range(M): | |
| tmp = [list(map(int, input().split())) for _ in range(4)] | |
| shark_dir.append(tmp) | |
| grid2 = [[None]*N for _ in range(N)] # (shark num, remaining sec) | |
| shark_info = [None for _ in range(M+1)] # cor x, cor y, cor dir | |
| for i in range(N): | |
| for j in range(N): | |
| num = grid[i][j] | |
| if num == 0: | |
| grid2[i][j] = (-1, -1) | |
| else: | |
| grid2[i][j] = (num, k) | |
| shark_info[num] = (i, j, direction[num]) | |
| DXDY = [None, (-1, 0), (1, 0), (0, -1), (0, 1)] | |
| INF = 0 # emtpy grid == INF; empty grid2 == -1 | |
| def possible_move(shark_num, cur_x, cur_y, cur_dir): | |
| """ | |
| find posible cor according to grid2, i.e., smell | |
| if has no smell, then return it | |
| if all has smell, if has mine, then return mine | |
| if not possible, return (-1, -1, -1) | |
| """ | |
| # check smell using direction priority | |
| flag = True | |
| my_smell = [] | |
| for nxt_dir in shark_dir[shark_num][cur_dir-1]: | |
| dx, dy = DXDY[nxt_dir] | |
| nxt_x, nxt_y = cur_x+dx, cur_y+dy | |
| # in the grid? | |
| if 0<=nxt_x<N and 0<=nxt_y<N: | |
| tmp_num, _ = grid2[nxt_x][nxt_y] | |
| # no smell or mine? | |
| if tmp_num == -1: | |
| flag = False | |
| return (nxt_x, nxt_y, nxt_dir) | |
| if tmp_num == shark_num: | |
| my_smell.append((nxt_x, nxt_y, nxt_dir)) | |
| if flag: | |
| if len(my_smell) > 0: | |
| return my_smell[0] | |
| else: | |
| return (-1, -1, -1) | |
| def update_grid2(): | |
| """ | |
| update grid2 according to finalized grid | |
| 무조건 -1 sec인데, 만약 동일 shark가 또 왔다면, 4로 update | |
| """ | |
| global grid, grid2 | |
| for i in range(N): | |
| for j in range(N): | |
| num, sec = grid2[i][j] | |
| gnum = grid[i][j] | |
| if gnum == num: # check if same shark | |
| sec = k+1 | |
| elif gnum != INF: # have shark | |
| num = gnum | |
| sec = k+1 | |
| elif gnum == INF: # empty | |
| pass | |
| sec -= 1 | |
| if sec <= 0: # check if empty | |
| num, sec = -1, -1 | |
| grid2[i][j] = (num, sec) | |
| def update_shark_info(): | |
| """ | |
| move to next cor according to grid2 | |
| can be overlapping with each other | |
| update shark info | |
| update grid | |
| update grid2 | |
| """ | |
| global grid, shark_info | |
| cnt = 0 | |
| for shark_num in range(1, M+1): # starting 1 | |
| cur_x, cur_y, cur_dir = shark_info[shark_num] | |
| if cur_x == None: | |
| continue | |
| nxt_x, nxt_y, nxt_dir = possible_move(shark_num, cur_x, cur_y, cur_dir) | |
| # no where to go | |
| if nxt_x == -1: | |
| shark_info[shark_num] = (None,None,None) | |
| continue | |
| tmp_num = grid[nxt_x][nxt_y] | |
| if tmp_num >= shark_num or tmp_num == INF: # check grid: if shark_num is smaller or empty | |
| grid[nxt_x][nxt_y] = shark_num # update grid nxt cor | |
| grid[cur_x][cur_y] = INF # update grid cur cor | |
| shark_info[shark_num] = [nxt_x, nxt_y, nxt_dir] # update shark_info | |
| cnt += 1 | |
| else: # check grid: if shark_num is bigger | |
| grid[cur_x][cur_y] = INF # dead | |
| shark_info[shark_num] = (None,None,None) # dead | |
| update_grid2() # update grid2 | |
| return True if cnt == 1 else False # True if only shark 1 survived | |
| past = 0 | |
| flag = False | |
| while not flag: | |
| past += 1 | |
| flag = update_shark_info() | |
| if past == 1001: | |
| past = -1 | |
| break | |
| print(past) | |
| ############################ | |
| # 청소년 상어 | |
| # https://www.acmicpc.net/submit/19236/ | |
| ############################ | |
| import copy | |
| from collections import deque | |
| def calc_dicrection(direction): | |
| if direction == 1: | |
| dx, dy = -1, 0 | |
| if direction == 2: | |
| dx, dy = -1, -1 | |
| if direction == 3: | |
| dx, dy = 0, -1 | |
| if direction == 4: | |
| dx, dy = 1, -1 | |
| if direction == 5: | |
| dx, dy = 1, 0 | |
| if direction == 6: | |
| dx, dy = 1, 1 | |
| if direction == 7: | |
| dx, dy = 0, 1 | |
| if direction == 8: | |
| dx, dy = -1, 1 | |
| return dx, dy | |
| def calc_shark_dicrection(direction): | |
| if direction == 1: | |
| dx, dy = [-1, -2, -3], [0, 0, 0] | |
| if direction == 2: | |
| dx, dy = [-1, -2, -3], [-1, -2, -3] | |
| if direction == 3: | |
| dx, dy = [0, 0, 0], [-1, -2, -3] | |
| if direction == 4: | |
| dx, dy = [1, 2, 3], [-1, -2, -3] | |
| if direction == 5: | |
| dx, dy = [1, 2, 3], [0, 0, 0] | |
| if direction == 6: | |
| dx, dy = [1, 2, 3], [1, 2, 3] | |
| if direction == 7: | |
| dx, dy = [0, 0, 0], [1, 2, 3] | |
| if direction == 8: | |
| dx, dy = [-1, -2, -3], [1, 2, 3] | |
| return dx, dy | |
| def get_grid_info(status): | |
| grid_info = {} | |
| for i in range(4): | |
| for j in range(4): | |
| _v, _d = status[i][j] | |
| if _v <= 0: | |
| continue | |
| grid_info[_v] = [_d, i, j] | |
| return grid_info | |
| def update_fish(status_copy): | |
| """info와 grid둘다 바꿔야함""" | |
| fish_info = get_grid_info(status_copy) | |
| f_ks = list(fish_info.keys()) | |
| for num in sorted(f_ks): | |
| direction, x, y = fish_info[num] | |
| ori_dir = direction | |
| flag = True | |
| while flag: | |
| dx, dy = calc_dicrection(direction) | |
| nxt_x, nxt_y = x+dx, y+dy | |
| if 0<=nxt_x<4 and 0<=nxt_y<4: # can move | |
| tmp_num, tmp_dir = status_copy[nxt_x][nxt_y] | |
| if not tmp_num == -1: # not shark | |
| # change grid | |
| status_copy[nxt_x][nxt_y] = [num, direction] | |
| status_copy[x][y] = [tmp_num, tmp_dir] | |
| # change info | |
| fish_info[num] = [direction, nxt_x, nxt_y] | |
| fish_info[tmp_num] = [tmp_dir, x, y] | |
| flag = False | |
| elif tmp_num == -1: #shark -> cannot move -> change dir | |
| direction += 1 | |
| direction = 1 if direction > 8 else direction | |
| else: #cannot move | |
| direction += 1 | |
| direction = 1 if direction > 8 else direction | |
| if direction == ori_dir: | |
| break | |
| return status_copy | |
| # grid = [] | |
| # for _ in range(4): | |
| # l = list(map(int, input().split())) | |
| # tmp = [] | |
| # for i in range(0, 4*2, 2): | |
| # tmp.append((l[i:i+2])) | |
| # grid.append(tmp) | |
| grid = [[[7, 6], [2, 3], [15, 6], [9, 8]], | |
| [[3, 1], [1, 8], [14, 7], [10, 1]], | |
| [[6, 1], [13, 6], [4, 3], [11, 4]], | |
| [[16, 1], [8, 7], [5, 2], [12, 2]]] | |
| max_score = 0 | |
| f_num, f_dir = grid[0][0] | |
| grid[0][0] = [-1, f_dir] | |
| max_score += f_num | |
| grid = update_fish(grid) | |
| q = deque([[max_score, grid, 0, 0, f_dir]]) | |
| while q: | |
| score, status, x, y, direction = q.popleft() | |
| # shark move | |
| dxs, dys = calc_shark_dicrection(direction) | |
| for dx, dy in zip(dxs, dys): | |
| nxt_x, nxt_y = x+dx, y+dy | |
| if 0<=nxt_x<4 and 0<=nxt_y<4: # can move | |
| status_copy = copy.deepcopy(status) | |
| f_num, f_dir = status_copy[nxt_x][nxt_y] | |
| if f_num > 0: | |
| status_copy[nxt_x][nxt_y] = [-1, f_dir] | |
| status_copy[x][y] = [0, 0] | |
| new_score = score + f_num | |
| # fish move | |
| status_copy = update_fish(status_copy) | |
| q.append([new_score, status_copy, nxt_x, nxt_y, f_dir]) | |
| max_score = max(max_score, new_score) | |
| print(max_score) | |
| ############################ | |
| # 치킨배달 | |
| # https://www.acmicpc.net/problem/15686 | |
| ############################ | |
| from itertools import combinations | |
| import math | |
| N, M = map(int, input().split()) | |
| grid = [list(map(int, input().split())) for _ in range(N)] | |
| home = []; kfcs = []; | |
| for i in range(N): | |
| for j in range(N): | |
| if grid[i][j] == 1: | |
| home.append((i, j)) | |
| elif grid[i][j] == 2: | |
| kfcs.append((i, j)) | |
| cost_dict = {} | |
| for h_x, h_y in home: | |
| for k_x, k_y in kfcs: | |
| cost = abs(h_x-k_x)+abs(h_y-k_y) | |
| cost_dict[(h_x, h_y, k_x, k_y)] = cost | |
| ans = math.inf | |
| for kfc in combinations(kfcs, M): | |
| tmp = 0 | |
| # find min dist from home x, y to kfc | |
| for h_x, h_y in home: | |
| min_dist = math.inf | |
| for k_x, k_y in kfc: | |
| min_dist = min(min_dist, cost_dict[(h_x, h_y, k_x, k_y)]) | |
| tmp += min_dist # min dist from home to kfc | |
| if ans < tmp: | |
| continue | |
| ans = min(ans, tmp) | |
| print(ans) | |
| ############################ | |
| # 아기상어 | |
| # https://www.acmicpc.net/problem/16236 | |
| ############################ | |
| import math | |
| import heapq | |
| N = 6 | |
| grid = [[5, 4, 3, 2, 3, 4], | |
| [4, 3, 2, 3, 4, 5], | |
| [3, 2, 9, 5, 6, 6], | |
| [2, 1, 2, 3, 4, 5], | |
| [3, 2, 1, 6, 5, 4], | |
| [6, 6, 6, 6, 6, 6]] | |
| # N = 10 | |
| # grid = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], | |
| # [1, 1, 1, 1, 1, 1, 1, 1, 1, 9]] | |
| # N = int(input()) | |
| # grid = [list(map(int, input().split())) for _ in range(N)] | |
| def search_nearest(start, cur_size): | |
| """가능 영역 전부 visit; 먹었을 떄 step을 tracking; 먹었을 때 dist로 min dist -> filter""" | |
| print("########IN###########", start) | |
| flag = True | |
| visited = []; q = []; dist=0 | |
| visited.append(start) | |
| heapq.heappush(q, (dist, start)) # (총step, cur위치) | |
| tmp = []; min_dist = math.inf | |
| while q: | |
| cur_dist, (cur_x, cur_y) = heapq.heappop(q) | |
| for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: | |
| nxt_x, nxt_y = cur_x+dx, cur_y+dy | |
| if 0<=nxt_x<N and 0<=nxt_y<N and (nxt_x, nxt_y) not in visited: | |
| if grid[nxt_x][nxt_y] <= cur_size: | |
| updated_dist = cur_dist+1 | |
| if updated_dist <= min_dist: | |
| visited.append((nxt_x, nxt_y)) | |
| heapq.heappush(q, (updated_dist, (nxt_x, nxt_y))) | |
| if 0 < grid[nxt_x][nxt_y] < cur_size: | |
| tmp.append((updated_dist, nxt_x, nxt_y)) | |
| min_dist = updated_dist | |
| print("########OUT###########") | |
| return tmp # [(dist, x, y), ....] | |
| start = None | |
| for i in range(N): | |
| for j in range(N): | |
| v = grid[i][j] | |
| if v > 0: | |
| if v == 9: | |
| start = (i, j) | |
| grid[i][j] = 0 | |
| continue | |
| sec = 0; n_eat=0; cur_size=2 | |
| while True: | |
| # target search | |
| for _g in grid: | |
| print(_g) | |
| res = search_nearest(start, cur_size) | |
| if len(res) < 1: | |
| break | |
| res = sorted(res, key=lambda x: (x[0], x[1], x[2])) | |
| print(res) | |
| res = res[0] | |
| next_location = res | |
| sec += res[0] | |
| start = (res[1], res[2]) | |
| n_eat += 1 | |
| if n_eat == cur_size: | |
| cur_size += 1 | |
| n_eat = 0 | |
| grid[start[0]][start[1]] = 0 | |
| print(sec) | |
| ############################ | |
| # 아기상어 | |
| # https://www.acmicpc.net/problem/3190 | |
| ############################ | |
| from collections import defaultdict | |
| from bisect import bisect_right, bisect_left | |
| def solution(words, queries): | |
| w_q = defaultdict(list) | |
| w_q_r = defaultdict(list) | |
| for w in words: | |
| _len = len(w) | |
| w_q[_len].append(w) | |
| w_q_r[_len].append(w[::-1]) | |
| for k in w_q: | |
| w_q[k].sort() | |
| w_q_r[k].sort() | |
| answer = [] | |
| for q in queries: | |
| # xxxx? | |
| if q[0] != '?': | |
| aa = q.replace('?', 'a') | |
| zz = q.replace('?', 'z') | |
| left = bisect_left(w_q[len(q)], aa) | |
| right = bisect_right(w_q[len(q)], zz) | |
| answer.append(right-left) | |
| # ?xxx | |
| else: | |
| q = q[::-1] | |
| aa = q.replace('?', 'a') | |
| zz = q.replace('?', 'z') | |
| left = bisect_left(w_q_r[len(q)], aa) | |
| right = bisect_right(w_q_r[len(q)], zz) | |
| answer.append(right-left) | |
| return answer | |
| ############################ | |
| # 여행경로 | |
| # https://programmers.co.kr/learn/courses/30/lessons/43164# | |
| ############################ | |
| N = int(input()) | |
| K = int(input()) | |
| cor = [] | |
| for _ in range(K): | |
| a, b = map(int, input().split()) | |
| cor.append((a, b)) | |
| rotation = {} | |
| L = int(input()) | |
| for _ in range(L): | |
| x, c = input().split() | |
| rotation[int(x)] = c | |
| N,K,cor,rotation,L = 6, 3, [(3, 4), (2, 5), (5, 3)], {3: 'D', 15: 'L', 17: 'D'}, 3 | |
| N,K,cor,rotation,L = 10, 4, [(1, 2), (1, 3), (1, 4), (1, 5)], {8: 'D', 10: 'D', 11: 'D', 13: 'L'}, 4 | |
| def do_move(path, do_rotation=None, direction=None): | |
| """ | |
| direction: 상하좌우 U,D,LL,RR | |
| """ | |
| # head go | |
| # if | |
| is_dead = False | |
| x, y = path[-1] # head | |
| #print(direction) | |
| # do rotation | |
| if do_rotation == 'L': # 왼쪽 | |
| if direction == 'U': | |
| direction = 'LL' | |
| elif direction == 'DD': | |
| direction = 'RR' | |
| elif direction == 'LL': | |
| direction = 'DD' | |
| elif direction == 'RR': | |
| direction = 'U' | |
| elif do_rotation == 'D': # 오른쪽 | |
| if direction == 'U': | |
| direction = 'RR' | |
| elif direction == 'DD': | |
| direction = 'LL' | |
| elif direction == 'LL': | |
| direction = 'U' | |
| elif direction == 'RR': | |
| direction = 'DD' | |
| if direction == 'U': | |
| xx, yy = x-1, y | |
| elif direction == 'DD': | |
| xx, yy = x+1, y | |
| elif direction == 'LL': | |
| xx, yy = x, y-1 | |
| elif direction == 'RR': | |
| xx, yy = x, y+1 | |
| if 0 < xx <= N and 0 < yy <= N: | |
| # face body | |
| if (xx, yy) in path: | |
| is_dead = True | |
| # have apple | |
| elif (xx, yy) in cor: | |
| cor.pop(cor.index((xx, yy))) | |
| path.append((xx, yy)) | |
| # no apple | |
| elif (xx, yy) not in cor: | |
| path.pop(0) | |
| path.append((xx, yy)) | |
| else: | |
| is_dead = True | |
| #print(xx, ',' ,yy, do_rotation, direction, is_dead) | |
| return path, is_dead, direction | |
| cnt = 0 | |
| do_rotation = None; is_dead = False | |
| path = [(1, 1)]; direction = 'RR' | |
| while not is_dead: | |
| cnt += 1 | |
| path, is_dead, direction = do_move(path, do_rotation=do_rotation, direction=direction) | |
| do_rotation = None | |
| #print(cnt, do_rotation, path, is_dead, direction) | |
| if cnt in rotation: | |
| do_rotation = rotation[cnt] | |
| continue | |
| print(cnt) | |
| ############################ | |
| # 여행경로 | |
| # https://programmers.co.kr/learn/courses/30/lessons/43164# | |
| ############################ | |
| from collections import defaultdict | |
| tickets = [["A", "B"], ["B", "D"], ["B", "C"], ["D", "B"]] | |
| tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] | |
| def solution(tickets): | |
| graph = defaultdict(list) | |
| for a, b in tickets: | |
| graph[a].append(b) | |
| for a in graph: | |
| graph[a].sort() | |
| stack = ['ICN']; path = [] | |
| while stack: | |
| cur = stack[-1] | |
| if len(graph[cur]) == 0 or cur not in graph: | |
| cur = stack.pop() | |
| path.append(cur) | |
| else: | |
| nxt = graph[cur].pop(0) | |
| stack.append(nxt) | |
| return path[::-1] | |
| def solution(tickets): | |
| # ticket 나열 | |
| tickets.sort(key = lambda x:x[1]) | |
| print(tickets) | |
| table = [i for i in range(len(tickets)) if tickets[i][0] == 'A'] | |
| table = [i for i in range(len(tickets)) if tickets[i][0] == 'ICN'] | |
| print([x for x in range(len(tickets))]) | |
| print(table) | |
| answer = 0 | |
| for s in table:# s: start ticket | |
| if answer !=0: | |
| break | |
| q = deque([[s]]) | |
| while q: | |
| print(q) | |
| path = q.popleft() | |
| print(path) | |
| if len(path) == len(tickets): | |
| answer = [tickets[i][0] for i in path] + [tickets[path[-1]][1]] | |
| break | |
| cur_arrival = path[-1] | |
| # print(lst) | |
| for ticket_idx in range(len(tickets)): | |
| if ticket_idx not in path: # 지금 완성된 path에 없는 ticket | |
| if tickets[cur_arrival][1] == tickets[ticket_idx][0]: #지금 도착지 == 해당 티켓 다음 출발지 | |
| q.append(path+[ticket_idx]) | |
| return answer | |
| ############################ | |
| # 경쟁적 전염 | |
| # https://www.acmicpc.net/source/15173493 | |
| ############################ | |
| target = 1000 - int(input()) | |
| ans = [0]*1001 | |
| coins = [500, 100, 50, 10, 5, 1] | |
| #greedy | |
| ans = 0 | |
| rem = target | |
| for c in coins: | |
| ans += rem//c | |
| rem = rem%c | |
| #DP | |
| for c in coins: | |
| ans[c] = 1 | |
| for i in range(1, 1000+1): | |
| if ans[i] != 0: | |
| continue | |
| tmp = ans[i-1] + 1 | |
| if i % 500 == 0: | |
| tmp = min(tmp, ans[i-500]+1) | |
| if i % 100 == 0: | |
| tmp = min(tmp, ans[i-100]+1) | |
| if i % 50 == 0: | |
| tmp = min(tmp, ans[i-50]+1) | |
| if i % 10 == 0: | |
| tmp = min(tmp, ans[i-10]+1) | |
| if i % 5 == 0: | |
| tmp = min(tmp, ans[i-5]+1) | |
| ans[i] = tmp | |
| print(ans[target]) | |
| ############################ | |
| # 경쟁적 전염 | |
| # https://www.acmicpc.net/source/14502 | |
| ############################ | |
| import heapq | |
| N, K = map(int, input().split()) | |
| grid = [list(map(int, input().split())) for _ in range(N)] | |
| S, X, Y = map(int, input().split()) | |
| q = [] | |
| for i in range(N): | |
| for j in range(N): | |
| v = grid[i][j] | |
| if v > 0: | |
| heapq.heappush(q, (v, i, j)) | |
| def virus(grid, q): | |
| q2 = [] | |
| while q: | |
| v, x, y = heapq.heappop(q) | |
| for dx, dy in zip([0,0,-1,1], [-1,1,0,0]): | |
| xx, yy = x+dx, y+dy | |
| if 0 <= xx < N and 0 <= yy < N: | |
| if grid[xx][yy] == 0: | |
| grid[xx][yy] = v | |
| heapq.heappush(q2, (v, xx, yy)) | |
| return q2 | |
| for _ in range(S): | |
| q = virus(grid, q) | |
| if len(q) < 1: | |
| break | |
| print(grid[X-1][Y-1]) | |
| ############################ | |
| # 연구소 | |
| #https://www.acmicpc.net/source/14502 | |
| ############################ | |
| from itertools import combinations | |
| from collections import deque | |
| def init(grid): | |
| tmp = [[0]*M for _ in range(N)] | |
| for i in range(N): | |
| for j in range(M): | |
| tmp[i][j] = grid[i][j] | |
| return tmp | |
| def dfs(virus, grid, cnt): | |
| stack = [(_x, _y) for _x, _y in virus] | |
| while stack: | |
| x, y = stack.pop() | |
| for (dx, dy) in zip([0,0,-1,1], [1,-1,0,0]): | |
| xx, yy = x+dx, y+dy | |
| if 0 <= xx < N and 0 <= yy < M: | |
| if grid[xx][yy] == 0: | |
| grid[xx][yy] = 2 | |
| stack.append((xx, yy)) | |
| cnt -= 1 | |
| return cnt | |
| N, M = map(int, input().split()) | |
| grid = [] | |
| for _ in range(N): | |
| l = list(map(int, input().split())) | |
| grid.append(l) | |
| cand = []; virus = []; n_zero = 0 | |
| for i in range(N): | |
| for j in range(M): | |
| if grid[i][j] == 0: | |
| cand.append((i, j)) | |
| n_zero += 1 | |
| if grid[i][j] == 2: | |
| virus.append((i, j)) | |
| ans = 0 | |
| for l in combinations(cand, 3): | |
| grid_copy = init(grid) | |
| # set wall | |
| for (x, y) in l: | |
| grid_copy[x][y] = 1 | |
| # unleash virus | |
| ori_val = sum(map(sum, grid_copy)) | |
| tmp = dfs(virus, grid_copy, n_zero-3) | |
| ans = max(ans, tmp) | |
| print(ans) | |
| ############################ | |
| # 백준 원판돌리기 | |
| # https://www.acmicpc.net/source/15812980 | |
| ############################ | |
| # mine wrong | |
| from copy import deepcopy | |
| def rotate(ori_mat, args): | |
| mat = deepcopy(ori_mat) | |
| x, d, k = args | |
| print(x, d, k) | |
| is_clock = True if d == 0 else False | |
| # x배수 원판돌림 | |
| for c_i in range(x, N+1, x): | |
| tmp = mat[c_i]; res = [INF]+[0]*M | |
| # do rotation | |
| if not is_clock: | |
| tmp = [INF] + list(reversed(tmp[1:])) | |
| move_step = k%M | |
| updated_idx = [M if (i+move_step)%M == 0 else (i+move_step)%M for i in range(1, M+1)] | |
| for i, j in enumerate(updated_idx, 1): | |
| res[j] = tmp[i] | |
| # update matrix | |
| if not is_clock: | |
| res = [INF] + list(reversed(res[1:])) | |
| mat[c_i] = res | |
| return mat | |
| def _traverse(mat, start, visited): | |
| cnt = 0; flag2 = True | |
| q2 = [start] | |
| q = deque([start]) | |
| while q: | |
| print(q) | |
| (x, y) = q.popleft() | |
| for dx, dy in zip([0,0,-1,1], [-1,1,0,0]): | |
| xx = x+dx | |
| yy = 1 if y+dy==M else y+dy | |
| if not (xx, yy) in visited: | |
| continue | |
| if 0<xx<M+1 and 0<yy<M+1: | |
| if not visited[(xx, yy)]: | |
| visited[(xx, yy)] = True | |
| q.append((xx,yy)) | |
| q2.append((xx,yy)) | |
| cnt += 1 | |
| if cnt > 0: | |
| flag2 = False | |
| for (x, y) in q2: | |
| mat[x][y] = INF | |
| return mat, flag2 | |
| def _make_num_dict(mat): | |
| num_dict = {} | |
| for i in range(1, N+1): | |
| for j in range(1, M+1): | |
| num = mat[i][j] | |
| if num == INF: | |
| continue | |
| if not num in num_dict: | |
| num_dict[num] = [] | |
| num_dict[num].append((i,j)) | |
| return num_dict | |
| def update_mat(mat): | |
| """update matrix per rotation""" | |
| num_dict = _make_num_dict(mat) | |
| flag = False | |
| for v, ls in num_dict.items(): # ls = [(), (), ...] | |
| if len(ls) < 2: | |
| continue | |
| visited = {i:False for i in ls} | |
| print(v, ls) | |
| for start in ls: | |
| mat, flag2 = _traverse(mat, start, visited) | |
| flag = flag or flag2 | |
| if flag: | |
| total_sum = 0; denominator = 0 | |
| for v, ls in num_dict.items(): | |
| total_sum += v*len(ls) | |
| denominator += len(ls) | |
| avg = total_sum/denominator | |
| for v, ls in num_dict.items(): | |
| for (x, y) in ls: | |
| if v > avg: | |
| mat[x][y] = max(mat[x][y]-1, 1) | |
| else: | |
| mat[x][y] += 1 | |
| return mat | |
| def solution(mat, rot_args): | |
| for i in range(1, T+1): | |
| mat = rotate(mat, rot_args[i]) | |
| mat = update_mat(mat) | |
| print(mat) | |
| return mat | |
| INF = 0 | |
| mat = [[], [INF, 1, 1, 2, 3], [INF, 5, 2, 4, 2], [INF, 3, 1, 3, 5], [INF, 2, 1, 3, 2]] | |
| rot_args = [[], [2, 0, 1]] | |
| ans = solution(mat, rot_args) | |
| t_sum = 0 | |
| for l in ans: | |
| t_sum += sum(l) | |
| t_sum | |
| # 모범답안 | |
| MIS = lambda: map(int,input().split()) | |
| def to_erase(): | |
| P = [] | |
| for i in range(n): | |
| for j in range(m): | |
| if board[i][j] == board[i][j-1] != 0: P.append((i,j,i,j-1)) | |
| for i in range(n-1): | |
| for j in range(m): | |
| if board[i][j] == board[i+1][j] != 0: P.append((i,j,i+1,j)) | |
| return P | |
| def control_average(): | |
| tot = n*m - sum(R.count(0) for R in board) | |
| if tot == 0: return | |
| avg = sum(map(sum, board)) / tot | |
| for R in board: | |
| for i in range(m): | |
| if 0 < R[i] < avg: R[i]+= 1 | |
| elif R[i] > avg: R[i]-= 1 | |
| n, m, T = MIS() | |
| board = [list(MIS()) for i in range(n)] | |
| for ROT in range(T): | |
| x, d, k = MIS() | |
| if d == 1: k = m-k | |
| for i in range(x-1, n, x): | |
| board[i] = board[i][-k:] + board[i][:-k] | |
| P = to_erase() | |
| if P: | |
| for i1,j1,i2,j2 in P: board[i1][j1] = board[i2][j2] = 0 | |
| else: control_average() | |
| print(sum(map(sum, board))) | |
| ############################ | |
| # rotate matix | |
| ############################ | |
| mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] | |
| for l in mat: | |
| print(l) | |
| def rotate_mat(mat): | |
| row = len(mat) | |
| col = len(mat[0]) | |
| res = [[0]*row for _ in range(col)] | |
| for r in range(row): | |
| for c in range(col): | |
| res[c][row-r-1] = mat[r][c] # clockwise | |
| # res[col-c-1][r] = a[i][j] # anti-clockwise | |
| return res | |
| print() | |
| for l in rotate_mat(mat): | |
| print(l) | |
| ############################ | |
| # 카카오2020 | |
| # 4 가사검색색 | |
| ############################ | |
| from bisect import bisect_right, bisect_left | |
| def init(words): | |
| words_ls = [[] for _ in range(10001)] | |
| words_rev = [[] for _ in range(10001)] | |
| for w in words: | |
| l = len(w) | |
| words_ls[l].append(w) | |
| words_rev[l].append(w[::-1]) | |
| for i in range(10001): | |
| words_ls[i] = sorted(words_ls[i]) | |
| words_rev[i] = sorted(words_rev[i]) | |
| return words_ls, words_rev | |
| def bisectfunc(q, words_ls): | |
| ii, jj = bisect_left(words_ls, q.replace('?', 'a')), bisect_right(words_ls, q.replace('?', 'z')) | |
| return jj - ii | |
| def is_pre(q): | |
| """prefix: 000??""" | |
| return q[0] != '?' | |
| def solution(words, queries): | |
| words_ls, words_rev = init(words) | |
| answer = [] | |
| for q in queries: | |
| if len(words_ls[len(q)]) == 0: | |
| answer.append(0) | |
| continue | |
| if is_pre(q): | |
| res = bisectfunc(q, words_ls[len(q)]) | |
| else: | |
| res = bisectfunc(q[::-1], words_rev[len(q)]) | |
| answer.append(res) | |
| return answer | |
| words = ["fro", "frodo", "front", "frost", "frozen", "frame", "kakao"] | |
| queries = ["fro??", "????o", "fr???", "fro???", "pro?"] | |
| solution(queries, words) | |
| ############################ | |
| # p399 | |
| # 45 | |
| ############################ | |
| # mine | |
| import heapq | |
| import sys | |
| input = sys.stdin.readline | |
| def find_root(root, a): | |
| if a != root[a]: | |
| root[a] = find_root(root, root[a]) | |
| return root[a] | |
| def union(root, a, b): | |
| a = find_root(root, a) | |
| b = find_root(root, b) | |
| if a > b: | |
| root[b] = a | |
| else: | |
| root[a] = b | |
| N = int(input()) | |
| M = N - 1 | |
| nodes = [] | |
| for i in range(N): | |
| x, y, z = map(int, input().split()) | |
| nodes.append((x, y, z, i)) | |
| # cost pair (cost, a, b) | |
| q = [] | |
| for axis in range(3): | |
| nodes = sorted(nodes, key=lambda x: x[axis]) | |
| prev = nodes[0] | |
| for i in range(1, N): | |
| cur = nodes[i] | |
| cost = abs(prev[axis]-cur[axis]) | |
| # heapq.heappush(q, (cost, prev[-1], cur[-1])) # (cost, a, b) | |
| q.append((cost, prev[-1], cur[-1])) # (cost, a, b) | |
| prev = cur | |
| q = sorted(q) | |
| # union find | |
| root = [i for i in range(N)] | |
| n_edge = 0 | |
| ans = 0 | |
| # while q and n_edge < M: | |
| # # cost, a, b = heapq.heappop(q) | |
| # cost, a, b = q.pop() | |
| # a = find_root(root, a) | |
| # b = find_root(root, b) | |
| # if a != b: | |
| # union(root, a, b) | |
| # n_edge += 1 | |
| # ans += cost | |
| # print(ans) | |
| for cost, a, b in q: | |
| a = find_root(root, a) | |
| b = find_root(root, b) | |
| if a != b: | |
| union(root, a, b) | |
| n_edge += 1 | |
| ans += cost | |
| if n_edge == M: | |
| break | |
| print(ans) | |
| # 모범답안 | |
| import collections | |
| import sys | |
| input=sys.stdin.readline | |
| def find(parent,node): | |
| if parent[node] == node: | |
| return node; | |
| return find(parent,parent[node]) | |
| def union(parent, x, y): | |
| x = find(parent,x) | |
| y = find(parent,y) | |
| #작은 수를 부모로 삼음 | |
| if x <y: | |
| parent[y] = x | |
| return x | |
| else: | |
| parent[x] = y | |
| return y | |
| def findParent(parent, x,y): | |
| x = find(parent,x) | |
| y = find(parent,y) | |
| if x == y: | |
| return True | |
| else: | |
| return False | |
| def kruskal(edges): | |
| result = 0 | |
| for w, s, e in edges: | |
| if findParent(parent, s, e): | |
| continue | |
| else: | |
| result+= w | |
| union(parent, s, e) | |
| return result | |
| N = int(input()) | |
| planets = [] | |
| edges = [] | |
| parent = [k for k in range(N)] | |
| for i in range(N): | |
| x, y, z = map(int, input().split()) | |
| planets.append((x,y,z,i)) | |
| for i in range(3): | |
| planets.sort(key = lambda x:x[i]) | |
| pre = planets[0] | |
| for j in range(1,N): | |
| cur = planets[j] | |
| edges.append((abs(pre[i]-cur[i]),pre[3],cur[3])) | |
| pre =cur | |
| edges.sort(key=lambda x:x[0]) | |
| ans =kruskal(edges) | |
| print(ans) | |
| ############################ | |
| # KAKAO 2021 | |
| # 합승택시 | |
| ############################ | |
| import math | |
| import heapq | |
| def dijk(start_node, start_cost, opt_distance, graph): | |
| q = [] | |
| heapq.heappush(q, (start_node, start_cost)) | |
| opt_distance[start_node] = start_cost | |
| while q: | |
| cur, cost_from_s_to_m = heapq.heappop(q) | |
| if opt_distance[cur] < cost_from_s_to_m: | |
| continue | |
| for (node_n, cost_from_m_to_n) in graph[cur]: | |
| updated_cost = cost_from_s_to_m + cost_from_m_to_n | |
| if updated_cost < opt_distance[node_n]: | |
| opt_distance[node_n] = updated_cost | |
| heapq.heappush(q, (node_n, updated_cost)) | |
| return opt_distance | |
| def solution(n, s, a, b, fares): | |
| table = [[] for i in range(n+1)] | |
| for l in fares: | |
| _a,_b,_c = l | |
| table[_a].append((_b, _c)) | |
| table[_b].append((_a, _c)) | |
| distance = [math.inf for _ in range(n+1)] | |
| distance1 = [math.inf for _ in range(n+1)] | |
| distance2 = [math.inf for _ in range(n+1)] | |
| distance = dijk(s, 0, distance, table) | |
| distance1 = dijk(a, 0, distance1, table) | |
| distance2 = dijk(b, 0, distance2, table) | |
| # min(s to a + a to b, s to k + k to a + k to b) | |
| answer = math.inf | |
| for k in range(1, n+1): | |
| answer = min(answer, distance[a]+distance[b], distance[k] + distance1[k] + distance2[k]) | |
| return answer | |
| ############################ | |
| # floyd warshall | |
| # from n to m | |
| # iter k node (n to k, k to m) | |
| ############################ | |
| n, m = 4, 7 | |
| # graph = [] # a to b; value == cost | |
| # for _ in range(n+1): | |
| # graph.append([math.inf]*(n+1)) | |
| graph = [[0, inf, inf, inf, inf], | |
| [inf, 0, 4, inf, 6], | |
| [inf, 3, 0, 7, inf], | |
| [inf, 5, inf, 0, 4], | |
| [inf, inf, inf, 2, 0]] | |
| for _ in range(m): | |
| a, b, c = map(int, input().split()) | |
| graph[a][b] = c | |
| ############### key algorithm | |
| for k in range(n+1): | |
| for a in range(n+1): | |
| for b in range(n+1): | |
| graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) | |
| ############### key algorithm | |
| for a in range(1, n+1): | |
| for b in range(1, n+1): | |
| if graph[a][b] == math.inf: | |
| print("inf", end = ' ') | |
| else: | |
| print(graph[a][b], end=' ') | |
| print() | |
| ############################ | |
| # dijk | |
| # from start to n | |
| ############################ | |
| distance = [math.inf] * (n + 1) | |
| graph = [[], | |
| [(2, 2), (3, 5), (4, 1)], | |
| [(3, 3), (4, 2)], | |
| [(2, 3), (6, 5)], | |
| [(3, 3), (5, 1)], | |
| [(3, 1), (6, 2)], | |
| []] | |
| distance = [math.inf] * (n + 1) | |
| def dijk(start, optimal_cost=distance): | |
| q = [] | |
| heapq.heappush(q, start) | |
| distance[start[0]] = start[1] | |
| while q: | |
| cur, from_s_to_cur_cost = heapq.heappop(q) | |
| if optimal_cost[cur] < from_s_to_cur_cost: # already visited, i.e., cost has already been applied to it | |
| continue | |
| for (node_m, from_cur_to_m_cost) in graph[cur]: | |
| updated_cost_from_s_to_m = from_s_to_cur_cost + from_cur_to_m_cost | |
| if updated_cost_from_s_to_m < optimal_cost[node_m]: | |
| optimal_cost[node_m] = updated_cost_from_s_to_m | |
| heapq.heappush(q, (node_m, updated_cost_from_s_to_m)) | |
| dijk((1, 0)) | |
| ############################ | |
| # KAKAO 2021 | |
| # 신규 아이디 추천 | |
| ############################ | |
| from itertools import combinations | |
| from collections import defaultdict | |
| def solution(orders, course): | |
| cnt = defaultdict(int) | |
| for n_elem in course: | |
| for ord_elem in orders: | |
| for l in combinations(sorted(list(ord_elem)), n_elem): | |
| cnt[l] += 1 | |
| ans = {k: 2 for k in course} | |
| for k, v in cnt.items(): | |
| if v > ans[len(k)]: | |
| ans[len(k)] = v | |
| res = [] | |
| for k, v in cnt.items(): | |
| if ans[len(k)] == v: | |
| res.append(''.join(k)) | |
| return sorted(res) | |
| from itertools import combinations | |
| from collections import defaultdict, Counter | |
| def solution(orders, course): | |
| ans = [] | |
| for n_elem in course: | |
| temp = [] | |
| for ord_elem in orders: | |
| temp.extend([l for l in combinations(sorted(list(ord_elem)), n_elem)]) | |
| if len(temp) < 1: | |
| continue | |
| res = Counter(temp) | |
| max_v = max([v for k, v in res.items()]+[2]) | |
| ans += [''.join(k) for k, v in res.items() if v == max_v] | |
| return sorted(ans) | |
| ############################ | |
| # KAKAO 2021 | |
| # 신규 아이디 추천 | |
| ############################ | |
| import re | |
| def solution(new_id): | |
| st = new_id | |
| st = st.lower() | |
| st = re.sub('[^a-z0-9\-_.]', '', st) | |
| st = re.sub('\.+', '.', st) | |
| st = re.sub('^[.]|[.]$', '', st) | |
| st = 'a' if len(st) == 0 else st[:15] | |
| st = re.sub('^[.]|[.]$', '', st) | |
| st = st if len(st) > 2 else st + "".join([st[-1] for i in range(3-len(st))]) | |
| return st | |
| def solution(new_id): | |
| new_id = new_id.lower() | |
| res = re.findall('[0-9a-zA-Z\-\_.]', new_id) | |
| new_id = ''.join(res) | |
| new_id = re.sub('[.]{2,}', '.', new_id) | |
| new_id = re.sub('^[.]|[.]$', '', new_id) | |
| if len(new_id) == 0: | |
| new_id = 'a' | |
| if len(new_id) >= 16: | |
| new_id = new_id[:15] | |
| new_id = re.sub('[.]$', '', new_id) | |
| if len(new_id) <= 2: | |
| while True: | |
| new_id += new_id[-1] | |
| if len(new_id) == 3: | |
| break | |
| return new_id | |
| ############################ | |
| # p298 | |
| # find union | |
| ############################ | |
| N, M = 7, 8 | |
| data = [list(map(int, input().split())) for _ in range(M)] | |
| data = [[0, 1, 3], | |
| [1, 1, 7], | |
| [0, 7, 6], | |
| [1, 7, 1], | |
| [0, 3, 7], | |
| [0, 4, 2], | |
| [0, 1, 1], | |
| [1, 1, 1]] | |
| root = [i for i in range(N+1)] | |
| def find_root(root, node): | |
| if node != root[node]: | |
| root[node] = find_root(root, root[node]) | |
| return root[node] | |
| def union_root(a, b): | |
| global root | |
| a = find_root(root, a) | |
| b = find_root(root, b) | |
| if a > b: | |
| root[b] = a | |
| else: | |
| root[a] = b | |
| for l in data: | |
| if l[0] == 0: | |
| union_root(l[1], l[2]) | |
| else: | |
| if find_root(root, l[1]) == find_root(root, l[2]): | |
| print('YES') | |
| else: | |
| print('NO') | |
| ############################ | |
| # 45 | |
| # https://www.acmicpc.net/problem/3665 | |
| ############################ | |
| from collections import deque | |
| def solution(n_team, rank, m_rev_order, rev): | |
| graph = [[] for _ in range(n_team+1)] | |
| for j, elem in enumerate(rank): | |
| if j == 0: | |
| continue | |
| for jj in range(0, j): | |
| graph[elem].append(rank[jj]) | |
| # reverse | |
| for pair in rev: | |
| flag = False | |
| second, first = pair | |
| if first not in graph[second]: | |
| flag = True | |
| if not flag: | |
| graph[first].append(second) | |
| idx = graph[second].index(first) | |
| graph[second].pop(idx) | |
| else: | |
| graph[second].append(first) | |
| idx = graph[first].index(second) | |
| graph[first].pop(idx) | |
| # indegree | |
| indeg = [0]*(n_team+1) | |
| for node, neighbor in enumerate(graph): | |
| for neig in neighbor: | |
| indeg[neig] += 1 | |
| # while | |
| res = [] | |
| starter = [j for j, val in enumerate(indeg) if j != 0 and val == 0] | |
| q = deque(starter) | |
| n_iter = 0 | |
| not_certain = False | |
| not_possible = False | |
| while q: | |
| n_iter += 1 | |
| cur = q.popleft() | |
| res.append(cur) | |
| for next_node in graph[cur]: | |
| indeg[next_node] -= 1 | |
| if indeg[next_node] == 0: | |
| q.append(next_node) | |
| if len(q) > 1: | |
| not_certain = True | |
| break | |
| if n_iter < n_team: | |
| not_possible = True | |
| if not_certain == True: | |
| print('?') | |
| elif not_possible == True: | |
| print('IMPOSSIBLE') | |
| else: | |
| for i in res[::-1]: | |
| print(i, end=' ') | |
| for tc in range(int(input())): | |
| n_team = int(input()) | |
| rank = list(map(int, input().split())) | |
| m_rev_order = int(input()) | |
| rev = [tuple(map(int, input().split())) for _ in range(m_rev_order)] | |
| solution(n_team, rank, m_rev_order, rev) | |
| ############################ | |
| # p303 | |
| # https://programmers.co.kr/learn/courses/30/lessons/92341 | |
| ############################ | |
| import math | |
| typed = ['5', | |
| '10 -1', | |
| '10 1 -1', | |
| '4 1 -1', | |
| '4 3 1 -1', | |
| '3 3 -1',] | |
| N = int(typed[0]) | |
| graph = [[] for _ in range(N+1)] | |
| indegree = [0] * (N+1) | |
| time = [0] * (N+1) | |
| for node, l in enumerate(typed[1:], 1): | |
| data = list(map(int, l.split())) | |
| time[node] = data[0] | |
| if len(data) > 1: | |
| for elem in data[1:-1]: | |
| graph[elem].append(node) | |
| indegree[node] += 1 | |
| q = deque([j for j, i in enumerate(indegree) if (i == 0) and (j != 0)]) | |
| # mine | |
| time_temp = [-1] * (N+1) | |
| while q: | |
| cur = q.popleft() | |
| for next_node in graph[cur]: | |
| # temporalily save time for next_node | |
| indegree[next_node] -= 1 | |
| time_temp[next_node] = max(time_temp[next_node], time[cur]) | |
| # update actual time for next_node | |
| if indegree[next_node] == 0: | |
| time[next_node] += time_temp[next_node] | |
| q.append(next_node) | |
| # anser | |
| ans = [i for i in time] | |
| while q: | |
| cur = q.popleft() | |
| for next_node in graph[cur]: | |
| ans[next_node] = max(ans[next_node], ans[next_node] + time[cur]) | |
| indegree[next_node] -= 1 | |
| if indegree[next_node] == 0: | |
| q.append(next_node) | |
| ############################ | |
| # 92341 | |
| # https://programmers.co.kr/learn/courses/30/lessons/92341 | |
| ############################ | |
| from math import ceil | |
| def diff(a, b): | |
| [a1, a2], [b1, b2] = a.split(':'), b.split(':') | |
| h = int(b1) - int(a1) | |
| m = 60*h + int(b2) - int(a2) | |
| return m | |
| def calc_cum(ls): | |
| """calculate cum mins for each car""" | |
| res = 0 | |
| if len(ls) % 2 != 0: | |
| ls.append('23:59') | |
| for i in range(2, len(ls)+1, 2): | |
| a, b = ls[i-2:i] | |
| m = diff(a, b) | |
| res += m | |
| return res | |
| def solution(fees, records): | |
| base_hour, base_fee, unit_hour, unit_fee = fees | |
| plate_dict = {} # store records for each car | |
| for elem in records: | |
| times, car_plate, car_record = elem.split() | |
| if car_plate not in plate_dict: | |
| plate_dict[car_plate] = [] | |
| plate_dict[car_plate].append(times) | |
| m_dict = {j: i for i, j in enumerate(sorted(plate_dict, key=lambda i: int(i)))} # mapping dict: car2id | |
| ans = [0]*len(m_dict) | |
| for key in plate_dict: | |
| cum_m = calc_cum(plate_dict[key]) | |
| if cum_m < base_hour: | |
| ans[m_dict[key]] += base_fee | |
| else: | |
| add_fee = ceil((cum_m - base_hour) / unit_hour) * unit_fee | |
| ans[m_dict[key]] += base_fee + add_fee | |
| return ans | |
| ############################ | |
| # 92335 | |
| # https://programmers.co.kr/learn/courses/30/lessons/92335 | |
| ############################ | |
| def is_prime(n): | |
| if n < 2: | |
| return False | |
| for i in range(2, int(n**0.5)+1): | |
| if n % i == 0: | |
| return False | |
| return True | |
| def convert(n, k): | |
| tmp = '' | |
| while n > 0: | |
| tmp += str(n % k) | |
| n //= k | |
| return tmp[::-1] | |
| def solution(n, k): | |
| n = convert(n, k) | |
| ans = 0 | |
| for sub in n.split('0'): | |
| if sub == '': | |
| continue | |
| if is_prime(int(sub)): | |
| ans += 1 | |
| continue | |
| return ans | |
| ############################ | |
| # 92334 | |
| # https://programmers.co.kr/learn/courses/30/lessons/92334 | |
| ############################ | |
| def solution(id_list, report, k): | |
| id_dict = {i: j for j, i in enumerate(id_list)} | |
| graph = [[] for _ in range(len(id_list))] | |
| penalty = [0] * len(id_list) | |
| ans = [0] * len(id_list) | |
| for l in set(report): | |
| a, b = l.split() | |
| graph[id_dict[b]].append(id_dict[a]) | |
| penalty[id_dict[b]]+=1 | |
| for _id, i in enumerate(penalty): | |
| if i >= k: | |
| for _id2 in graph[_id]: | |
| ans[_id2] += 1 | |
| return ans | |
| ############################ | |
| # 48; keyerror | |
| # https://www.acmicpc.net/submit/19237 | |
| ############################ | |
| import copy | |
| n, m, k = map(int, input().split()) | |
| #n, m, k = 4, 2, 6 | |
| arr = [] | |
| for _ in range(n): | |
| arr.append([int(i) for i in input().split()]) | |
| #arr = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2]] | |
| direction = {key: None for key in range(1, m+1)} | |
| init_dir = list(map(int, input().split())) | |
| for key, v in enumerate(init_dir): | |
| direction[key+1] = v | |
| #direction = {1: 4, 2: 3} | |
| prior_dir = {} | |
| for key in range(1, m+1): | |
| for j in range(1, 4+1): | |
| if key not in prior_dir: | |
| prior_dir[key] = {i: None for i in range(1,4+1)} | |
| inputs = list(map(int, input().split())) | |
| prior_dir[key][j] = inputs | |
| #prior_dir = {1: {1: [1, 2, 3, 4], 2: [2, 3, 4, 1], 3: [3, 4, 1, 2], 4: [4, 1, 2, 3]}, | |
| # 2: {1: [1, 2, 3, 4], 2: [2, 3, 4, 1], 3: [3, 4, 1, 2], 4: [4, 1, 2, 3]}} | |
| location = {} | |
| location_prev = {} | |
| for i in range(n): | |
| for j in range(n): | |
| if arr[i][j] > 0: | |
| location[arr[i][j]] = [i, j] | |
| location_prev[arr[i][j]] = [i, j] | |
| #location = {1: [0, 0], 2: [3, 3]} | |
| #location_prev = {1: [0, 0], 2: [3, 3]} | |
| perfume = [[[0, 0]]*n for _ in range(n)] | |
| for shark_n in location: | |
| x, y = location[shark_n] | |
| perfume[x][y] = [shark_n, k] | |
| #perfume = [[[1, 6], [0, 0], [0, 0], [0, 0]], | |
| # [[0, 0], [0, 0], [0, 0], [0, 0]], | |
| # [[0, 0], [0, 0], [0, 0], [0, 0]], | |
| # [[0, 0], [0, 0], [0, 0], [2, 6]]] | |
| dxdy_dict = {1: [-1, 0], 2: [1, 0], 3:[0, -1], 4: [0, 1]} | |
| def search_my_perfume(shark_n, x, y): | |
| perfume_ls = [] | |
| for key in dxdy_dict: | |
| dx, dy = dxdy_dict[key] | |
| nx, ny = x+dx, y+dy | |
| if 0 <= nx < n and 0 <= ny < n: | |
| if perfume[nx][ny][0] == shark_n: | |
| perfume_ls.append(key) | |
| return perfume_ls | |
| def move_shark(): | |
| # previous_arr = copy.deepcopy(arr) | |
| for shark_n in sorted(direction): | |
| moved = False | |
| d = direction[shark_n] | |
| for dd in prior_dir[shark_n][d]: | |
| x, y = location[shark_n] | |
| # search | |
| dx, dy = dxdy_dict[dd] | |
| nx, ny = x+dx, y+dy | |
| if 0 <= nx < n and 0 <= ny < n: | |
| # empty; no perfume | |
| # update: location | |
| # 마지막에 check하고 arr에 반영 | |
| if arr[nx][ny] == 0 and perfume[nx][ny][0] == 0: | |
| location_prev[shark_n] = [x, y] | |
| location[shark_n] = [nx, ny] | |
| direction[shark_n] = dd | |
| moved = True | |
| break | |
| if not moved: | |
| # 빈칸없음 | |
| possible_dir = search_my_perfume(shark_n, x, y) | |
| for dd in prior_dir[shark_n][d]: | |
| if dd in possible_dir: | |
| location_prev[shark_n] = [x, y] | |
| dx, dy = dxdy_dict[dd] | |
| nx, ny = x+dx, y+dy | |
| location[shark_n] = [nx, ny] | |
| direction[shark_n] = dd | |
| break | |
| def update_vars(): | |
| """ | |
| update arr, perfume | |
| """ | |
| killed = [] | |
| for shark_n in sorted(location): | |
| x, y = location[shark_n] | |
| if arr[x][y] == 0: | |
| arr[x][y] = shark_n | |
| perfume[x][y] = [shark_n, k+1] | |
| x, y = location_prev[shark_n] | |
| arr[x][y] = 0 | |
| else: # kill | |
| killed.append(shark_n) | |
| del location[shark_n] # del killed shark info from location | |
| x, y = location_prev[shark_n] | |
| arr[x][y] = 0 | |
| del location_prev[shark_n] | |
| # update perfume | |
| for i in range(n): | |
| for j in range(n): | |
| if perfume[i][j][1] == k+1: | |
| perfume[i][j][1] = k | |
| continue | |
| if 0 < perfume[i][j][1] < k+1: | |
| perfume[i][j][1] -= 1 | |
| if perfume[i][j][1] == 0: | |
| perfume[i][j][0] = 0 | |
| n_iter = 1000 | |
| cnt = 0 | |
| for _ in range(n_iter): | |
| cnt += 1 | |
| move_shark() | |
| update_vars() | |
| if len(location) == 1: | |
| n_iter = 0 | |
| print(cnt) | |
| break | |
| if n_iter == 999: | |
| print(-1) | |
| ############################ | |
| # 32; DP 런타임에러 | |
| # https://www.acmicpc.net/submit/14501 | |
| ############################ | |
| n = int(input()) | |
| dp = [[int(j) for j in input().split(' ')] for _ in range(1, n+1)] | |
| for i in range(1, n): # 1, 2, 3, ... row | |
| for j in range(0, i+1): # if i==3, 1, 2, 3 | |
| if j == 0: | |
| dp[i][j] = dp[i][j] + dp[i-1][j] | |
| elif j == i: | |
| dp[i][j] = dp[i][j] + dp[i-1][j-1] | |
| else: | |
| dp[i][j] = dp[i][j] + max(dp[i-1][j-1], dp[i-1][j]) | |
| print(max(dp[i])) | |
| ############################ | |
| # 31; DP 왜안됨? | |
| ############################ | |
| n, m = 4, 4 | |
| val = [int(i) for i in input().split(' ')] | |
| mat = [[0]*(m+1) for _ in range(n+1)] | |
| cnt = 0 | |
| for i in range(1, n+1): | |
| for j in range(1, m+1): | |
| mat[i][j] = val[cnt] | |
| cnt += 1 | |
| dp = [[0]*(m+1) for _ in range(n+1)] | |
| dx = [0, 1, -1] | |
| dy = [-1, -1, -1] | |
| for i in range(1, n+1): | |
| for j in range(1, m+1): | |
| intercept = 0 | |
| for xx, yy in zip(dx, dy): | |
| if (0 < (i+xx) < n) and (0 < (j+yy) < m): | |
| intercept = max(intercept, dp[i+xx][j+yy]) | |
| dp[i][j] = mat[i][j] + intercept | |
| ############################ | |
| # 30; | |
| ############################ | |
| from bisect import bisect_left, bisect_right | |
| def count_by_range(arr, left_val, right_val): | |
| left_idx = bisect_left(arr, left_val) | |
| right_idx = bisect_left(arr, right_val) | |
| return right_idx - left_idx | |
| def solution(words, queries): | |
| bins = [[] for i in range(100001)] | |
| bins_reversed = [[] for i in range(100001)] | |
| for w in words: | |
| bins[len(w)].append(w) | |
| bins_reversed[len(w)].append(w[::-1]) | |
| for i in range(100001): | |
| bins[i].sort() | |
| bins_reversed[i].sort() | |
| answer = [] | |
| for q in queries: | |
| if q[0] =='?': | |
| ans = count_by_range(bins_reversed[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?', 'z')) | |
| else: | |
| ans = count_by_range(bins[len(q)], q.replace('?', 'a'), q.replace('?', 'z')) | |
| answer.append(ans) | |
| return answer | |
| ############################ | |
| # 16: bfs; 좌표; 런타임에러 | |
| ############################ | |
| from collections import deque | |
| from itertools import combinations | |
| import copy | |
| N, M = 7, 7 | |
| original_arr =[[2, 0, 0, 0, 1, 1, 0], | |
| [0, 0, 1, 0, 1, 2, 0], | |
| [0, 1, 1, 0, 1, 0, 0], | |
| [0, 1, 0, 0, 0, 0, 0], | |
| [0, 0, 0, 0, 0, 1, 1], | |
| [0, 1, 0, 0, 0, 0, 0], | |
| [0, 1, 0, 0, 0, 0, 0]] | |
| N, M = [int(i) for i in input().split(' ')] | |
| arr = [] | |
| for _ in range(n): | |
| arr.append([int(i) for i in input().split(' ')]) | |
| v_cor = [] | |
| n_cor = [] | |
| num_wall = 0 | |
| for i in range(N): | |
| for j in range(M): | |
| if original_arr[i][j] == 2: | |
| v_cor.append((i, j)) | |
| elif original_arr[i][j] == 1: | |
| num_wall += 1 | |
| else: | |
| n_cor.append((i, j)) | |
| dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] | |
| def bfs(start): | |
| """ | |
| start should be virus-cor | |
| """ | |
| num_v = 0 | |
| q = deque([]) | |
| for s in start: | |
| q.append(s) | |
| while q: | |
| x, y = q.popleft() | |
| for xx, yy in zip(dx, dy): | |
| nx, ny = x+xx, y+yy | |
| # 벽은 뚫을 수 없음 | |
| if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0: | |
| arr[nx][ny] = 2 | |
| q.append((nx, ny)) | |
| num_v += 1 | |
| return num_v | |
| def udpate_arr(wall_cor): | |
| """ | |
| wall_cor = ((),(),()) | |
| """ | |
| arr = copy.deepcopy(original_arr) | |
| for i, j in wall_cor: | |
| arr[i][j] = 1 | |
| return arr | |
| wall_cand = list(combinations(n_cor, 3)) | |
| min_v = 1e9 | |
| for wall_cor in wall_cand: | |
| arr = udpate_arr(wall_cor) | |
| num_v = bfs(v_cor) | |
| if num_v < min_v: | |
| min_v = num_v | |
| ans = N*M - min_v -2 - num_wall - 3 | |
| ans | |
| ############################ | |
| # 46: bfs; 좌표; 최단거리 | |
| ############################ | |
| from collections import deque | |
| INF = 1e9 | |
| n = 4 | |
| arr = [[4, 3, 2, 1], [0, 0, 0, 0], [0, 0, 9, 0], [1, 2, 3, 4]] | |
| def find_target(dist): | |
| """ | |
| 가장 가까운 target 찾기 | |
| return coordinate, distance_value | |
| """ | |
| target_x, target_y = 0, 0 | |
| min_dist = INF | |
| for i in range(n): | |
| for j in range(n): | |
| if (dist[i][j] != -1) and (min_dist > dist[i][j]) and (0 < arr[i][j] < cur_size): | |
| target_x, target_y = i, j | |
| min_dist = dist[target_x][target_y] | |
| if min_dist == INF: | |
| return None | |
| return target_x, target_y, min_dist | |
| dx, dy = [1, -1, 0, 0], [0, 0, -1, 1] | |
| def bfs(): | |
| global cur_x, cur_y, cur_size | |
| print(cur_x, cur_y, cur_size) | |
| distance = [[-1]*n for i in range(n)] | |
| q = deque() | |
| q.append((cur_x, cur_y)) | |
| distance[cur_x][cur_y] = 0 | |
| while q: | |
| x, y = q.popleft() | |
| for xx, yy in zip(dx, dy): | |
| if 0 <= x + xx < len(arr) and 0 <= y + yy < len(arr[0]) and cur_size >= arr[x+xx][y+yy]: | |
| if distance[x+xx][y+yy] == -1: | |
| distance[x+xx][y+yy] = distance[x][y] + 1 | |
| q.append((x+xx, y+yy)) | |
| return distance | |
| for i in range(n): | |
| for j in range(n): | |
| if arr[i][j] == 9: | |
| cur_x, cur_y = i, j | |
| arr[cur_x][cur_y] = 0 | |
| ate = 0; res = 0; cur_size = 2 | |
| while True: | |
| distance = bfs() | |
| print(distance) | |
| value = find_target(distance) | |
| if value == None: | |
| break | |
| else: | |
| cur_x, cur_y = value[0], value[1] | |
| res += value[2] | |
| arr[cur_x][cur_y] = 0 | |
| ate += 1 | |
| print(arr) | |
| if ate >= cur_size: | |
| cur_size += 1 | |
| ate = 0 | |
| ############################################## | |
| # p152; 미로탈출 | |
| # 최단거리 | |
| ############################################## | |
| arr = [[1,0,1,0,1,0], | |
| [1,1,1,1,1,1], | |
| [0,0,0,0,0,1], | |
| [1,1,1,1,1,1], | |
| [1,1,1,1,1,1]] | |
| dx = [0, 0, -1, 1] | |
| dy = [1, -1, 0, 0] | |
| target = (4, 5) | |
| def bfs(x, y, graph=arr): | |
| q = deque() | |
| q.append((x, y)) | |
| while q: | |
| x, y = q.popleft() | |
| for xx, yy in zip(dx, dy): | |
| if (0 <= x+xx < len(arr)) and (0 <= y+yy < len(arr[0])): | |
| nx, ny = x+xx, y + yy | |
| if graph[nx][ny] == 0: | |
| continue | |
| if graph[nx][ny] == 1: | |
| graph[nx][ny] = graph[x][y] + 1 | |
| q.append((nx, ny)) | |
| ############################################## | |
| # p203; 3 #################################### | |
| ############################################## | |
| N, M = 4, 6 | |
| arr = [19, 15, 10, 17] | |
| arr.sort() | |
| arr | |
| start, end = arr[0], arr[-1] | |
| mid = (start+end)//2 | |
| # mid 값을 이진탐색 | |
| # target M 만족하면 그만 | |
| while start <= end: | |
| # mid에 맞게 잘라 | |
| mid = (start+end)//2 | |
| res = 0 | |
| for v in arr: | |
| res += max((v-mid), 0) | |
| if res == M: | |
| break | |
| # res > M: mid 더 크게 | |
| elif res > M: | |
| start = mid + 1 | |
| # res > M: mid 더 크게 | |
| elif res < M: | |
| end = mid - 1 | |
| ############################################## | |
| # 15 ######################################### | |
| ############################################## | |
| graph = [[] for _ in range(V+1)] | |
| for t in [(1, 2), (1, 3), (2, 3), (2, 4)]: | |
| a, b = t | |
| graph[a].append(b) | |
| # bfs 그대로 진행하되 | |
| # distance를 tracking | |
| distance = [-1]*(n+1) | |
| q = deque([start]) | |
| distance[start] = 0 | |
| while q: | |
| now = q.popleft() | |
| for next_node in graph[now]: | |
| if distance[next_node] == -1: | |
| q.append(next_node) | |
| distance[next_node] = distance[now] + 1 | |
| for i, v in enumerate(distance): | |
| if v == k: | |
| print(i) | |
| ############################################## | |
| # 28 ######################################### | |
| ############################################## | |
| def anchor_search(arr, start, end): | |
| """탈출조건""" | |
| if start > end: | |
| return None | |
| mid = (end+start)//2 | |
| if arr[mid] == mid: | |
| return mid | |
| elif mid < arr[mid]: | |
| return anchor_search(arr, start, mid-1) | |
| elif mid > arr[mid]: | |
| return anchor_search(arr, mid+1, end) | |
| anchor_search([-15,-6,1,3,7], 0, 5) | |
| ############################################## | |
| # 44 ######################################### | |
| ############################################## | |
| # 최소신장알고리즘 | |
| def find_parent(parent, x): | |
| if parent[x] != x: | |
| parent[x] = find_parent(parent, parent[x]) | |
| return parent[x] | |
| def union_parent(parent, a, b): | |
| a = find_parent(parent, a) | |
| b = find_parent(parent, b) | |
| if a[0] >= b[0]: | |
| parent[b] = a | |
| else: | |
| parent[a] = b | |
| node = [(11, -15, -15), (14, -5, -15), (-1, -1, -5), (10, -4, -1), (19, -4, 19)] | |
| edge = [] | |
| for i, n in enumerate(node): | |
| if i == len(node): | |
| continue | |
| for _, n2 in enumerate(node[i+1:]): | |
| c = min([abs(i-j) for i, j in zip(n, n2)]) | |
| edge.append((c, n, n2)) | |
| edge.sort() | |
| parent = {n: n for n in node} | |
| res = 0 | |
| for edg in edge: | |
| c, n1, n2 = edg | |
| if not find_parent(parent, n1) == find_parent(parent, n2): | |
| union_parent(parent, n1, n2) | |
| res += c | |
| ############################################## | |
| # 46 ######################################### | |
| ############################################## | |
| # - 크루스칼: 최소신장트리알고리즘 | |
| # - 모든 노드를, 최소 비용으로 연결 | |
| # - 간선 sort | |
| # - cycle 안되도록 확인 | |
| # - find-union | |
| def find_root(parent, x): | |
| if parent[x] != x: | |
| parent[x] = find_root(parent, parent[x]) | |
| return parent[x] | |
| def union_g(parent, a, b): | |
| a = find_root(parent, a) | |
| b = find_root(parent, b) | |
| if a < b: | |
| parent[b] = a | |
| else: | |
| parent[a] = b | |
| def solution(): | |
| N, M = map(int, input().split()) | |
| mat = [tuple(map(int, input().split())) for _ in range(M)] | |
| parent = [0] * (N+1) | |
| for i in range(1, N+1): | |
| parent[i] = i | |
| total = 0; result = 0 | |
| for e in mat: | |
| a, b, cost = e | |
| total += cost | |
| if find_root(parent, a) != find_root(parent, b): | |
| union_g(parent, a, b) | |
| result += cost | |
| return total, result | |
| ############################################## | |
| # 27 ######################################### | |
| ############################################## | |
| def bi_search(arr, target, start, end): | |
| """ | |
| target이 중간아래 -> 왼쪽확인 start ~ mid-1 | |
| target이 중간위 -> 오른쪽확인 mid+1 ~ start | |
| """ | |
| if start > end: | |
| return -1 | |
| mid = (end+start)//2 | |
| # 찾았다 | |
| if arr[mid] == target: | |
| return mid | |
| # 크다 | |
| if arr[mid] > target: | |
| return bi_search(arr, target, start, mid-1) | |
| # 작다 | |
| if arr[mid] < target: | |
| return bi_search(arr, target, mid+1, end) | |
| def solution(): | |
| N, x = map(int, input().split()) | |
| arr = list(map(int, input().split())) | |
| res = 0 | |
| while True: | |
| idx = bi_search(arr, x, 0, len(arr)-1) | |
| if idx == -1: | |
| break | |
| arr.pop(idx) | |
| res += 1 | |
| return res if res>0 else -1 | |
| ############################################## | |
| # 26 ######################################### | |
| ############################################## | |
| N = int(input()) | |
| ls = [int(input()) for _ in range(N)] | |
| >> 3 | |
| >> 10 | |
| >> 20 | |
| >> 40 | |
| if N < 3: | |
| print(sum(ls)) | |
| else: | |
| ans = 0 | |
| prev_ = sum(ls[:2]) | |
| ans += prev_ | |
| for next_ in ls[2:]: | |
| sum_ = prev_ + next_ | |
| ans += sum_ | |
| prev_ = sum_ | |
| print(ans) | |
| ############################################## | |
| # 11 ######################################### | |
| ############################################## | |
| def update_dir(tunr_dir, current_direction): | |
| """ | |
| update direction according to the turn list | |
| up + left: left 3 | |
| down + left: right 4 | |
| left + left: down 2 | |
| right + left: up 1 | |
| up + right: right 4 | |
| down + right: left 3 | |
| left + right: up 1 | |
| right + right: down 2 | |
| """ | |
| if current_direction == 1: # up | |
| if tunr_dir == 'L': | |
| return 3 | |
| if tunr_dir == 'D': | |
| return 4 | |
| if current_direction == 2: # down | |
| if tunr_dir == 'L': | |
| return 4 | |
| if tunr_dir == 'D': | |
| return 3 | |
| if current_direction == 3: # left | |
| if tunr_dir == 'L': | |
| return 2 | |
| if tunr_dir == 'D': | |
| return 1 | |
| if current_direction == 4: # right | |
| if tunr_dir == 'L': | |
| return 1 | |
| if tunr_dir == 'D': | |
| return 2 | |
| def update_occupy(occupy, current, current_direction, cnt, K, turn_time, turn_dir, apple): | |
| """ | |
| return next coordinate | |
| - next corresponds to the current direction (1, 2, 3, 4) (상하좌우) | |
| - if next == apple: then append next to occupy | |
| """ | |
| if cnt in turn_time: #방향전환이라면, | |
| current_direction = update_dir(turn_dir[turn_time.index(cnt)], current_direction) | |
| # next coordinate | |
| if current_direction == 1: # up | |
| next_ = (current[0] -1, current[1] + 0) | |
| if current_direction == 2: # down | |
| next_ = (current[0] + 1, current[1] + 0) | |
| if current_direction == 3: # down | |
| next_ = (current[0] + 0, current[1] - 1) | |
| if current_direction == 4: # down | |
| next_ = (current[0] + 0, current[1] + 1) | |
| # check if next is done | |
| flag = check_done(next_, occupy, K) | |
| if flag: | |
| return occupy, next_ , flag, apple | |
| # update occupy according to apple | |
| occupy, apple = check_apple(next_, occupy, apple) | |
| print(current_direction) | |
| print(next_) | |
| print(occupy) | |
| return occupy, next_, flag, apple | |
| def check_done(next_, occupy, N): | |
| """ | |
| check if bump into snake itself or wall | |
| """ | |
| if next_[0] < 0 or next_[1] < 0: # wall | |
| return True | |
| if next_[0] > N or next_[1] > N: # wall | |
| return True | |
| if next_ in occupy:# itself | |
| return True | |
| return False | |
| def check_apple(next_, occupy, apple): | |
| """ | |
| return updated occupy | |
| """ | |
| if next_ not in apple: | |
| occupy.pop(0) # 꼬리 자르기 | |
| else: | |
| apple.pop(apple.index(next_)) # 사과 먹기 | |
| occupy.append(next_) | |
| return occupy, apple | |
| # initialization | |
| N = 6; K = 3 | |
| apple = [(3,4), (2,5), (5,3)] | |
| L = 3 | |
| snake = [(3, 'D'), (15, 'L'), (17, 'D')] | |
| next_ = (1, 2) | |
| occupy = [(1, 1)] | |
| current_direction = 4 | |
| turn_info = [(3, 'D'), (15, 'L'), (17, 'D')] | |
| turn_time = [i[0] for i in turn_info] | |
| turn_dir = [i[1] for i in turn_info] | |
| # turn_info2 = [(3, 'D'), (15, 'L'), (17, 'D')] | |
| cnt = 0 | |
| flag = False | |
| while not flag: | |
| # next update | |
| current = next_ | |
| occupy, next_, flag, apple = update_occupy(occupy, current, current_direction, cnt, N, turn_time=turn_time, turn_dir=turn_dir, apple=apple) | |
| cnt += 1 | |
| ############################################## | |
| # 12 ######################################### | |
| ############################################## | |
| def solution(N, build_frame): | |
| def check_column(N, cor, beam_cor, col_cor): | |
| """ | |
| 벗어나면 안됨 | |
| 바닥 위; beam의 끝; 다른 column위 | |
| """ | |
| nx, ny = cor | |
| if (not 0<= ny <=N) or (not 0<= nx <=N) or (not 0<= ny+1 <=N): | |
| return False | |
| if (ny == 0) or (cor in beam_cor['start']) or (cor in beam_cor['end']) or (cor in col_cor['end']): | |
| return True | |
| #print('fail', cor, col_cor, beam_cor) | |
| return False | |
| def check_beam(N, cor, beam_cor, col_cor): | |
| """ | |
| 바닥은 안됨 | |
| 한쪽 끝이 column위; 양쪽 끝이 beam와 연결 | |
| """ | |
| nx, ny = cor | |
| if (ny == 0) or (not 0<= ny <=N) or (not 0<= nx <=N) or (not 0<= nx+1 <=N): | |
| return False | |
| if ((nx, ny) in col_cor['end']) or ((nx+1, ny) in col_cor['end']) or ( ((nx, ny) in beam_cor['end']) and ((nx+1, ny) in beam_cor['start']) ): | |
| return True | |
| #print('fail', cor, col_cor, beam_cor) | |
| return False | |
| def processing(N, l, beam_cor, col_cor): | |
| x, y, a, b = l | |
| if b == 1: | |
| if a == 0: # column | |
| if check_column(N, (x, y), beam_cor, col_cor): | |
| col_cor['start'].append((x, y)) | |
| col_cor['end'].append((x, y+1)) | |
| if a == 1: # beam | |
| if check_beam(N, (x, y), beam_cor, col_cor): | |
| beam_cor['start'].append((x, y)) | |
| beam_cor['end'].append((x+1, y)) | |
| if b == 0: # delete | |
| if a == 0: # column a: 가능조건: 1) col: a end가 b start이면 안됨; | |
| if (x, y) in col_cor['start']: | |
| i_ = col_cor['start'].index((x, y)) | |
| col_cor['start'].pop(i_) | |
| i_ = col_cor['end'].index((x, y+1)) | |
| col_cor['end'].pop(i_) | |
| del_ok = validation(beam_cor, col_cor) | |
| if not del_ok: | |
| col_cor['start'].append((x, y)) | |
| col_cor['end'].append((x, y+1)) | |
| if a == 1: | |
| if (x, y) in beam_cor['start']: | |
| i_ = beam_cor['start'].index((x, y)) | |
| beam_cor['start'].pop(i_) | |
| i_ = beam_cor['end'].index((x+1, y)) | |
| beam_cor['end'].pop(i_) | |
| del_ok = validation(beam_cor, col_cor) | |
| if not del_ok: | |
| beam_cor['start'].append((x, y)) | |
| beam_cor['end'].append((x+1, y)) | |
| return beam_cor, col_cor | |
| def gen_frame(beam_cor, col_cor): | |
| ls = [] | |
| bc = [[i[0], i[1], 1] for i in beam_cor['start']] | |
| cc = [[i[0], i[1], 0] for i in col_cor['start']] | |
| ls.extend(bc) | |
| ls.extend(cc) | |
| return ls | |
| def validation(beam_cor, col_cor): | |
| """ | |
| 삭제 후 검증 | |
| """ | |
| #print(1) | |
| ls = gen_frame(beam_cor, col_cor) | |
| for l in ls: | |
| x, y, a = l | |
| if a == 0: # column | |
| is_ok = check_column(N, (x, y), beam_cor, col_cor) | |
| if a == 1: # beam | |
| is_ok = check_beam(N, (x, y), beam_cor, col_cor) | |
| if not is_ok: | |
| return False # stop delete | |
| return True # ok del | |
| beam_cor = {'start':[], 'end':[]} | |
| col_cor = {'start':[], 'end':[]} | |
| for l in build_frame: | |
| beam_cor, col_cor = processing(N, l, beam_cor, col_cor) | |
| ans = gen_frame(beam_cor, col_cor) | |
| ans = sorted(ans, key=lambda x: (x[0], x[1])) | |
| return ans | |
| ############################################## | |
| # 41 ######################################### | |
| ############################################## | |
| # 연결되어있는가? == root가 동일한가? | |
| def find_parent(parent, x): | |
| if parent[x] != x: | |
| parent[x] = find_parent(parent, parent[x]) | |
| return parent[x] | |
| def union(parent, a, b): | |
| """ | |
| select edge and update root | |
| """ | |
| a = find_parent(parent, a) | |
| b = find_parent(parent, b) | |
| if a < b: | |
| parent[b] = a | |
| else: | |
| parent[a] = b | |
| N, M = 5, 4 | |
| mat = [ | |
| [0, 1, 0, 1, 1], | |
| [1, 0, 1, 1, 0], | |
| [0, 1, 0, 0, 0], | |
| [1, 1, 0, 0, 0], | |
| [1, 0, 0, 0, 0], | |
| ] | |
| edge = [] | |
| for i in range(N): | |
| for j in range(i, N): | |
| if mat[i][j] == 1: | |
| edge.append((i, j)) | |
| parent = [0]*(N+1) | |
| for i in range(N+1): | |
| parent[i] = i | |
| for (a, b) in edge: | |
| union(parent, a, b) | |
| target = [2,3,4,3] | |
| root_v = parent[target[0]] | |
| for e in target: | |
| if parent[e] != root_v: | |
| print('NO') | |
| print('YES') | |
| ############################################## | |
| # 25 ######################################### | |
| ############################################## | |
| from collections import Counter | |
| def solution(N, stages): | |
| stages = sorted(stages, reverse=True) | |
| answer = {k:0 for k in range(1, N+1)} | |
| # define 1st elems | |
| denominator = 0 | |
| numerator = 0 | |
| prev = stages[0] | |
| # iter elems | |
| for i in range(len(stages)): | |
| # if num changed | |
| if stages[i] != prev: | |
| # update answer with previous numerator and denominator | |
| answer[prev] = numerator/denominator | |
| # update key | |
| prev = stages[i] | |
| # update numerator as 0 | |
| numerator = 0 | |
| # +1 denominator and numerator | |
| denominator += 1 | |
| numerator += 1 | |
| # update last value | |
| answer[prev] = numerator/denominator | |
| return [i[0] for i in sorted(answer.items(), key=lambda x: (x[1],-x[0]), reverse=True) if i[0] <= N] | |
| ############################################## | |
| # 10 ######################################### | |
| ############################################## | |
| def solution(key, lock): | |
| def padding_lock(key, lock): | |
| m = len(key) | |
| n = len(lock) | |
| padded = [] | |
| for i in range(m-1): | |
| padded.append([0]*(n+2*(m-1))) | |
| for l in lock: | |
| padded.append([0]*(m-1) + l + [0]*(m-1)) | |
| for i in range(m-1): | |
| padded.append([0]*(n+2*(m-1))) | |
| return padded | |
| def spatial_sum(key, lock_row, lock_col, target, lock_target): | |
| cnt_lock = 0 | |
| for i, j in target: | |
| if lock[lock_row+i][lock_col+j] + key[i][j] > 1: | |
| return False | |
| if (lock_row+i, lock_col+j) in lock_target: | |
| cnt_lock += 1 | |
| return True if cnt_lock == len(lock_target) else False | |
| def find_target(arg, is_key = True): | |
| if is_key: | |
| val = 1 | |
| else: | |
| val = 0 | |
| target = [] | |
| for i in range(len(arg)): | |
| for j in range(len(arg)): | |
| if arg[i][j] == val: | |
| target.append((i,j)) | |
| return target | |
| def rotation(key): | |
| temp = [] | |
| for i in range(len(key)): | |
| temp.append([l[i] for l in key[::-1]]) | |
| return temp | |
| lock_target = find_target(lock, is_key=False) | |
| lock_target = [(i+len(key)-1, j+len(key)-1) for i, j in lock_target] | |
| lock = padding_lock(key, lock) | |
| cnt = 0 | |
| bool_ = False | |
| while cnt < 4: | |
| for i in lock: | |
| print(i) | |
| for i in key: | |
| print(i) | |
| cnt += 1 | |
| target = find_target(key) | |
| for lock_pos_row in range(len(lock)-len(key)+1): | |
| for lock_pos_col in range(len(lock)-len(key)+1): | |
| bool_ = spatial_sum(key, lock_pos_row, lock_pos_col, target, lock_target) | |
| print(bool_) | |
| if bool_: | |
| return True | |
| key = rotation(key) | |
| return False | |
| ############################################## | |
| # 9 ######################################### | |
| ############################################## | |
| def solution(sent): | |
| def find_token(sent, n=1): | |
| if len(sent) == 1: | |
| return sent | |
| k = 1 | |
| new_str = '' | |
| for i in range(0, len(sent), n): | |
| span = sent[i:i+n] | |
| # 처음 단어는 패스 | |
| if i == 0: | |
| prev = span | |
| continue | |
| # 동일 ngram | |
| if prev == span: | |
| k += 1 | |
| # ngram변함: 새로운거 시작; | |
| if prev != span: | |
| # 이전꺼 k +=1 하고 반영; | |
| if k > 1: | |
| new_str += str(k) | |
| new_str += prev | |
| # 새로운 거 시작 | |
| prev = span | |
| k = 1 | |
| # 마지막 문자라면: 반영하고 끝냄 | |
| if i+n >=len(sent): | |
| if k > 1: | |
| new_str += str(k) | |
| new_str += prev | |
| # print(span, prev, new_str) | |
| return new_str | |
| min_ = len(sent) | |
| for n in range(1, min_): | |
| val = find_token(sent, n) | |
| if len(val) < min_: | |
| min_ = len(val) | |
| return min_ | |
| ############################################## | |
| # 22 ######################################### | |
| ############################################## | |
| q = [] | |
| status = 0 # 1: l; 0: -; | |
| start = (0, (0, 1, status)) # cost, coordinate | |
| heapq.heappush(q, start) | |
| distance[(x, y, s)] = 0 | |
| while q: | |
| print(q) | |
| c, (x, y, s) = heapq.heappop(q) | |
| c_prime = c + 1 | |
| if distance[(x, y, s)] < c: | |
| continue | |
| ############ status == 1 | |
| # 1 + up + right (rotation) | |
| x_next, y_next = x - 1, y + 1 | |
| flag = False if (0 <= x_next < len(mat) and 0 <= y_next < len(mat[0])) else True | |
| if (s == 1) and (not flag) and (mat[x_next][y_next-1] == 0 and mat[x_next][y_next] == 0 and mat[x_next+1][y_next] == 0): | |
| dist = distance[(x_next, y_next, 0)] | |
| if dist > c_prime: | |
| distance[(x_next, y_next, 0)] = c_prime | |
| heapq.heappush(q, (c_prime, (x_next, y_next, 0))) | |
| # 1 + right (rotation) | |
| x_next, y_next = x, y + 1 | |
| flag = False if (0 <= x_next < len(mat) and 0 <= y_next < len(mat[0])) else True | |
| if (s == 1) and (not flag) and (mat[x-1][y] == 0 and mat[x_next-1][y_next] == 0 and mat[x_next][y_next] == 0): | |
| dist = distance[(x_next, y_next, 0)] | |
| if dist > c_prime: | |
| distance[(x_next, y_next, 0)] = c_prime | |
| heapq.heappush(q, (c_prime, (x_next, y_next, 0))) | |
| # 1 + down | |
| x_next, y_next = x + 1, y | |
| flag = False if (0 <= x_next < len(mat) and 0 <= y_next < len(mat[0])) else True | |
| if (s == 1) and (not flag) and (mat[x-1][y] == 0 and mat[x_next][y_next] == 0): | |
| dist = distance[(x_next, y_next, 1)] | |
| if dist > c_prime: | |
| distance[(x_next, y_next, 1)] = c_prime | |
| heapq.heappush(q, (c_prime, (x_next, y_next, 1))) | |
| ############ status == 0 | |
| # 0 + down (rotation) | |
| x_next, y_next = x + 1, y | |
| flag = False if (0 <= x_next < len(mat) and 0 <= y_next < len(mat[0])) else True | |
| if (s == 0) and (not flag) and (mat[x][y-1] == 0 and mat[x_next-1][y_next-1] == 0 and mat[x_next][y_next] == 0): | |
| dist = distance[(x_next, y_next, 1)] | |
| if dist > c_prime: | |
| distance[(x_next, y_next, 1)] = c_prime | |
| heapq.heappush(q, (c_prime, (x_next, y_next, 1))) | |
| # 0 + down + left (rotation) | |
| x_next, y_next = x + 1, y - 1 | |
| flag = False if (0 <= x_next < len(mat) and 0 <= y_next < len(mat[0])) else True | |
| if (s == 0) and (not flag) and (mat[x][y-1] == 0 and mat[x_next][y_next+1] == 0 and mat[x_next][y_next] == 0): | |
| dist = distance[(x_next, y_next, 1)] | |
| if dist > c_prime: | |
| distance[(x_next, y_next, 1)] = c_prime | |
| heapq.heappush(q, (c_prime, (x_next, y_next, 1))) | |
| # 0 + right | |
| x_next, y_next = x, y + 1 | |
| flag = False if (0 <= x_next < len(mat) and 0 <= y_next < len(mat[0])) else True | |
| if (s == 0) and (not flag) and (mat[x][y-1] == 0 and mat[x_next][y_next] == 0): | |
| dist = distance[(x_next, y_next, 0)] | |
| if dist > c_prime: | |
| distance[(x_next, y_next, 0)] = c_prime | |
| heapq.heappush(q, (c_prime, (x_next, y_next, 0))) | |
| ############################################## | |
| # 39 ######################################### | |
| ############################################## | |
| import heapq | |
| # cost matrix | |
| cost = [[5, 5, 4], | |
| [3, 9, 1], | |
| [3, 2, 7]] | |
| # make distance mat | |
| INF = int(1e9) | |
| distance = {} | |
| for i in range(len(cost)): | |
| for j in range(len(cost[0])): | |
| distance[(i, j)] = INF | |
| # dijkstrat | |
| q = [] | |
| i, j = (0, 0) | |
| start = (cost[i][j], (0, 0)) | |
| heapq.heappush(q, start) | |
| dx = [0, 0, -1, 1] | |
| dy = [-1, 1, 0, 0] | |
| while q: | |
| c, (x, y) = heapq.heappop(q) | |
| if distance[(x, y)] < c: | |
| continue | |
| # traverse u, d, l, r | |
| for vx, vy in zip(dx, dy): | |
| next_x, next_y = x + vx, y + vy | |
| if 0 <= next_x < len(cost) and 0 <= next_y < len(cost[0]): | |
| # previous cost | |
| dist = distance[(next_x, next_y)] | |
| # updated cost | |
| if dist > c + cost[next_x][next_y]: | |
| distance[(next_x, next_y)] = c + cost[next_x][next_y] | |
| heapq.heappush(q, (c + cost[next_x][next_y], (next_x, next_y))) | |
| ############################################## | |
| # p147 BFS ######################################### | |
| ############################################## | |
| mat = [[0,0,1,1,0], | |
| [0,0,0,1,1], | |
| [1,1,1,1,1], | |
| [0,0,0,0,0]] | |
| def traverse(k, is_visit): | |
| q = deque() | |
| x, y = k | |
| q.append((x, y)) | |
| while q: | |
| (x_, y_) = q.popleft() | |
| for vx, vy in zip(dx, dy): | |
| if (0 <= x_ + vx < len(mat)) and (0 <= y_ + vy < len(mat[0])): | |
| if not is_visit[(x_ + vx, y_ + vy)]: | |
| is_visit[(x_ + vx, y_ + vy)] = 1 | |
| q.append((x_ + vx, y_ + vy)) | |
| return is_visit | |
| is_visit = {} | |
| for i in range(len(mat)): | |
| for j in range(len(mat[0])): | |
| if mat[i][j] == 1: | |
| is_visit[(i, j)] = 1 | |
| else: | |
| is_visit[(i, j)] = 0 | |
| cnt = 0 | |
| keys = list(is_visit.keys()) | |
| for k in keys: | |
| if not is_visit[k]: | |
| print(k) | |
| cnt += 1 | |
| is_visit = traverse(k, is_visit) | |
| ############################################## | |
| # 6 ######################################### | |
| ############################################## | |
| def solution(food_times, k): | |
| t = {i: food_times[i] for i in range(len(food_times))} | |
| ls = []; cnt = 0; denominator = len(food_times) | |
| while len(ls) < sum(food_times): | |
| idx = cnt%denominator | |
| if t[idx] > 0: # 아직 남음 | |
| ls.append(idx) | |
| t[idx] -= 1 | |
| cnt +=1 | |
| if len(ls) == k+1: | |
| return ls[-1]+1 | |
| return -1 | |
| ############################################## | |
| # 7 ######################################### | |
| ############################################## | |
| a = [int(i) for i in str(123402)] | |
| print(a) | |
| pnt = int(len(a)/2 * 1) | |
| print(pnt) | |
| if sum(a[:pnt]) == sum(a[pnt:]): | |
| print('LUCKY') | |
| else: | |
| print('READY') | |
| ############################################## | |
| # 23 ######################################### | |
| ############################################## | |
| ls = [['j', '50', '80', '100'], ['S', '80', '60', '50'], ['s', '80', '70', '100']] | |
| ls.sort(key=lambda x: ( -int(x[1]), int(x[2]), -int(x[3]), x[0])) | |
| ############################################## | |
| # 5 ######################################### | |
| ############################################## | |
| N = 5; M = 3 | |
| w = [1,3,2,3,2] | |
| N = 8; M = 5 | |
| w = [1,5,4,3,2,4,5,2] | |
| cnt = 0 | |
| for i in range(N): | |
| if i == N: | |
| break | |
| for j in range(i+1, N): | |
| if w[i] != w[j]: | |
| cnt += 1 | |
| print(cnt) | |
| ############################################## | |
| # 21 ######################################### | |
| ############################################## | |
| import math | |
| N, L, R = 2, 20, 50 | |
| A = [[50, 30], [20, 40]] | |
| dp_down = [[0]*(N-1) for _ in range(N-1)] | |
| dp_right = [[0]*(N-1) for _ in range(N-1)] | |
| # down, right | |
| def update_dp(i_, j_): | |
| dx = [0, 1]; dy = [1, 0] | |
| v = A[i_][j_] | |
| # down | |
| x = i_ + dx[0]; y = j_ + dy[0] | |
| if x <= N or y <= N: | |
| v1 = A[x][y] | |
| if L <= math.abs(v-v1) <= R: | |
| dp_down[i][j] = 1 | |
| x = i_ + dx[1]; y = j_ + dy[1] | |
| if x <= N or y <= N: | |
| v1 = A[x][y] | |
| if L <= math.abs(v-v1) <= R: | |
| dp_right[i][j] = 1 | |
| def update_A(): | |
| for i in range(N): | |
| for j in range(N): | |
| pass | |
| for i in range(N): | |
| for j in range(N): | |
| update_dp(i, j) | |
| update_A() | |
| ############################################## | |
| # 37 ######################################### | |
| ############################################## | |
| # 왜틀림? | |
| # iter 한번만 해도 안바뀐다는 보장? | |
| table = [[1e9]*nc for _ in range(nc)] | |
| for t in cost: | |
| x, y = t | |
| table[x-1][y-1] = cost[t] | |
| for i in range(nc): | |
| for j in range(nc): | |
| if i == j: | |
| table[i][j]=0 | |
| # i -> k -> j | |
| # k를 거쳐가는 것들을 업데이트 | |
| for k in range(nc): | |
| for i in range(nc): | |
| for j in range(nc): | |
| table[i][j] = min(table[i][j], table[i][k]+table[k][j]) | |
| for i in range(nc): | |
| ls = [] | |
| for j in range(nc): | |
| ls.append(table[i][j]) | |
| print(ls) | |
| >>> | |
| [0, 2, 3, 2, 5] | |
| [12, 0, 15, 2, 5] | |
| [8, 9, 0, 2, 5] | |
| [10, 7, 13, 0, 3] | |
| [7, 4, 10, 6, 0] | |
| ############################################## | |
| # 4 ########################################## | |
| ############################################## | |
| import copy | |
| l = [1,1,2,3,9] | |
| a = [1,2,3,9] | |
| b = [2,1,1,1] | |
| memo = {} | |
| temp = {} | |
| possible_val = [] | |
| for i, v in enumerate(l): | |
| temp = copy.deepcopy(b) | |
| idx = a.index(v) | |
| temp[idx] -= 1 | |
| memo[tuple(temp)] = v | |
| possible_val.append(v) | |
| def update_dp(memo): | |
| global possible_val | |
| memo_temp = {} | |
| for tup, v in memo.items(): | |
| for j, t in enumerate(tup): | |
| if t == 0: | |
| continue | |
| temp = list(copy.deepcopy(tup)) | |
| temp[j] -= t | |
| memo_temp[tuple(temp)] = v + t | |
| possible_val.append(v+t) | |
| print(memo_temp) | |
| return memo_temp | |
| for _ in range(n): | |
| memo = update_dp(memo) | |
| >> | |
| {(0, 1, 1, 1): 2, | |
| (1, 0, 1, 1): 2, | |
| (1, 1, 0, 1): 2, | |
| (1, 1, 1, 0): 2, | |
| (0, 0, 1, 1): 4, | |
| (2, 0, 0, 1): 4, | |
| (2, 0, 1, 0): 10, | |
| (0, 1, 0, 1): 5, | |
| (2, 1, 0, 0): 10, | |
| (0, 1, 1, 0): 11} | |
| {(0, 0, 1, 1): 3, | |
| (0, 1, 0, 1): 3, | |
| (0, 1, 1, 0): 3, | |
| (1, 0, 0, 1): 3, | |
| (1, 0, 1, 0): 3, | |
| (1, 1, 0, 0): 3, | |
| (0, 0, 0, 1): 6, | |
| (0, 0, 1, 0): 12, | |
| (2, 0, 0, 0): 11, | |
| (0, 1, 0, 0): 12} | |
| {(0, 0, 0, 1): 4, | |
| (0, 0, 1, 0): 4, | |
| (0, 1, 0, 0): 4, | |
| (1, 0, 0, 0): 4, | |
| (0, 0, 0, 0): 13} | |
| {(0, 0, 0, 0): 5} | |
| {} | |
| for trg in range(1, l[-1]*n): | |
| if trg not in possible_val: | |
| print(trg) | |
| break | |
| ############################################## | |
| ### 20 ####################################### | |
| ############################################## | |
| import itertools | |
| n = 5 | |
| in_ = [[0,1,0,0,2],[2,0,1,0,0],[0,0,0,0,0],[0,2,0,0,0],[0,0,2,0,0]] | |
| n = 4 | |
| in_ = [[1,1,1,2],[0,0,0,0],[0,0,0,0],[2,2,2,0]] | |
| # find student, teacher, possible rock coordinate | |
| s_ls = []; t_ls = []; r_ls = [] | |
| for i in range(n): | |
| for j in range(n): | |
| if in_[i][j] == 1: | |
| s_ls.append((i, j)) | |
| elif in_[i][j] == 2: | |
| t_ls.append((i, j)) | |
| else: | |
| r_ls.append((i, j)) | |
| def check_block(s, t): | |
| """ | |
| - check (s_i, t_j) pair if student is killed | |
| - return False if student is killed | |
| - eg. (s_1, t_2) == False | |
| student vs teacher | |
| """ | |
| x, y = t | |
| s_x, s_y = s | |
| if x == s_x: # kill | |
| return False | |
| if y == s_y: # kill | |
| return False | |
| return True | |
| # key: killed (s, t) pair; <- need to protect | |
| # value: block rock coordinate; | |
| # check which pair is killed | |
| killed = [] # (s, t) | |
| for s in s_ls: | |
| for t in t_ls: | |
| res = check_block(s, t) | |
| if not res: | |
| killed.append((s, t)) | |
| is_visit = {i:0 for i in killed} | |
| # check if rock_candidate can block teacher | |
| def check_block(s,t,r): | |
| """ | |
| - check if rock_candidate can save student in killed pair | |
| - return True if rock works | |
| """ | |
| s_x, s_y = s | |
| t_x, t_y = t | |
| r_x, r_y = r | |
| if s_x == t_x: | |
| if (t_y < r_y < s_y) or (t_y > r_y > s_y): | |
| return True | |
| if s_y == t_y: | |
| if (t_x < r_x < s_x) or (t_x > r_x > s_x): | |
| return True | |
| return False | |
| # make dict: key rock; value saved pair in killed | |
| # eg. {(1, 4): [((1,2), (1,3)), ((1,4), (1,3)), ((1,6), (1,3))], ...} | |
| block_dict = {} | |
| for r in r_ls: | |
| for s, t in killed: | |
| if check_block(s, t, r): | |
| if r not in block_dict: | |
| block_dict[r] = [] | |
| block_dict[r].append((s, t)) | |
| # combine 3 iter working rock coordinate | |
| # len(killed) == len(saved by 3 rock) | |
| combination_rock = list(itertools.combinations(block_dict, 3)) | |
| for rocks in combination_rock: | |
| for r_ in rocks: | |
| for b_ in block_dict[r_]: | |
| is_visit[b_] = 1 | |
| if sum([i[1] for i in is_visit.items()]) == len(is_visit): | |
| print('Done') | |
| print(rocks) | |
| break | |
| print('None') | |
| ############################################## | |
| ### 36 edit distance ######################### | |
| ############################################## | |
| a = 'sunday' | |
| b = 'saturday' | |
| dp = [[i] + [0]*(len(a)) for i in range(len(b)+1)] | |
| dp[0] = list(range(len(a)+1)) | |
| dy = [0,-1,-1] | |
| dx = [-1,-1,0] | |
| for y in range(len(dp)): | |
| if y == 0: | |
| continue | |
| for x in range(len(dp[0])): | |
| if x == 0: | |
| continue | |
| # find min | |
| min_val = None | |
| for i in range(3): | |
| ny = y + dy[i] | |
| nx = x + dx[i] | |
| if min_val is None: | |
| min_val = dp[ny][nx] | |
| else: | |
| min_val = min(min_val, dp[ny][nx]) | |
| # check if prefix is equal to each other | |
| if a[x-1] == b[y-1]: | |
| dp[y][x] = min_val | |
| else: | |
| dp[y][x] = min_val+1 | |
| ############################################## | |
| ### 3 ####################################### | |
| ############################################## | |
| ls = list(map(int, list(input()))) | |
| prev = ls[0] | |
| ans = 0 | |
| for i in ls[1:]: | |
| if i != prev: | |
| ans += 1 | |
| prev = i | |
| print((ans+1)//2) | |
| # 19 | |
| # # bfs: visit adjacent | |
| # graph = { | |
| # 'A' : ['B','C'], | |
| # 'B' : ['D', 'E'], | |
| # 'C' : ['F'], | |
| # 'D' : [], | |
| # 'E' : ['F'], | |
| # 'F' : [] | |
| # } | |
| # visited = [] | |
| # q = [] | |
| # node = 'A' | |
| # visited.append(node) | |
| # q.append(node) | |
| # while q: | |
| # s = q.pop(0) | |
| # print(s) | |
| # for neigh in graph[s]: | |
| # if neigh not in visited: | |
| # visited.append(neigh) | |
| # q.append(neigh) | |
| # # permutation by dp | |
| from itertools import permutations | |
| op2 = [1,1,2,3,4] | |
| perm = permutations(op2) | |
| def calc(num_ls, op_ls): | |
| val = num_ls[0] | |
| for i, o in enumerate(op_ls, 1): | |
| if o == 1: | |
| val += num_ls[i] | |
| if o == 2: | |
| val -= num_ls[i] | |
| if o == 3: | |
| val //= num_ls[i] | |
| if o == 4: | |
| val *= num_ls[i] | |
| return val | |
| num_ls = [1,2,3,4,5,6] | |
| cand = [] | |
| per_ls = [i for i in perm] | |
| for o_ls in per_ls: | |
| res = calc(num_ls, o_ls) | |
| cand.append(res) | |
| print(res) | |
| print(max(cand), min(cand)) | |
| #35 답 | |
| n = 100 | |
| dp = [0]*n | |
| dp[0] = 1 | |
| i2 = i3 = i5 = 0 | |
| v2, v3, v5 = 2, 3, 5 | |
| for i in range(1, n): | |
| print('========') | |
| print(dp) | |
| print(v2, v3 ,v5) | |
| print(i2, i3 ,i5) | |
| dp[i] = min(v2, v3, v5) | |
| if dp[i] == v2: | |
| i2 += 1 | |
| v2 = dp[i2] * 2 | |
| if dp[i] == v3: | |
| i3 += 1 | |
| v3 = dp[i3] * 3 | |
| if dp[i] == v5: | |
| i5 += 1 | |
| v5 = dp[i5] * 5 | |
| >>> | |
| ======== | |
| [1, 0, 0, 0, 0, 0, 0, 0, 0, 0] | |
| 2 3 5 | |
| 0 0 0 | |
| ======== | |
| [1, 2, 0, 0, 0, 0, 0, 0, 0, 0] | |
| 4 3 5 | |
| 1 0 0 | |
| ======== | |
| [1, 2, 3, 0, 0, 0, 0, 0, 0, 0] | |
| 4 6 5 | |
| 1 1 0 | |
| ======== | |
| [1, 2, 3, 4, 0, 0, 0, 0, 0, 0] | |
| 6 6 5 | |
| 2 1 0 | |
| ======== | |
| [1, 2, 3, 4, 5, 0, 0, 0, 0, 0] | |
| 6 6 10 | |
| 2 1 1 | |
| ======== | |
| [1, 2, 3, 4, 5, 6, 0, 0, 0, 0] | |
| 8 9 10 | |
| 3 2 1 | |
| ======== | |
| [1, 2, 3, 4, 5, 6, 8, 0, 0, 0] | |
| 10 9 10 | |
| 4 2 1 | |
| ======== | |
| [1, 2, 3, 4, 5, 6, 8, 9, 0, 0] | |
| 10 12 10 | |
| 4 3 1 | |
| ======== | |
| [1, 2, 3, 4, 5, 6, 8, 9, 10, 0] | |
| 12 12 15 | |
| 5 3 2 | |
| ############################################## | |
| ### 35 ####################################### | |
| ############################################## | |
| n = 10000 | |
| dp = [0]*(n+1) | |
| dp[0] = 1 | |
| cand = [] | |
| for i in range(n): | |
| cand.extend([dp[i]*2, dp[i]*3, dp[i]*5]) | |
| cand = sorted(list(set(cand))) | |
| dp[i+1] = cand.pop(0) | |
| # 35-1 | |
| n=1000 | |
| dp2 = [] | |
| i = 0 | |
| while True: | |
| i += 1 | |
| val = 2 ** i | |
| if val > n: | |
| break | |
| dp2.append(val) | |
| dp3 = [] | |
| i = 0 | |
| while True: | |
| i += 1 | |
| val = 3 ** i | |
| if val > n: | |
| break | |
| dp3.append(val) | |
| dp5 = [] | |
| i = 0 | |
| while True: | |
| i += 1 | |
| val = 5 ** i | |
| if val > n: | |
| break | |
| dp5.append(val) | |
| dp23 = [] | |
| for val2 in dp2: | |
| for val3 in dp3: | |
| res = val2*val3 | |
| if res >= n: | |
| break | |
| dp23.append(res) | |
| dp25 = [] | |
| for val2 in dp2: | |
| for val5 in dp5: | |
| res = val2*val5 | |
| if res >= n: | |
| break | |
| dp25.append(res) | |
| dp35 = [] | |
| for val3 in dp3: | |
| for val5 in dp5: | |
| res = val3*val5 | |
| if res >= n: | |
| break | |
| dp35.append(res) | |
| dp235 = [] | |
| for val35 in dp35: | |
| for val2 in dp2: | |
| res = val2*val35 | |
| if res >= n: | |
| break | |
| dp235.append(res) | |
| print(sorted(dp2 + dp3 + dp5 + dp23 + dp25 + dp35 + dp235)) | |
| ############################################## | |
| ### 2 ####################################### | |
| ############################################## | |
| in_ = '02984' | |
| in_ = '567' | |
| # 0인지 확인 | |
| # 0 아니면 곱해 | |
| previous = 1 | |
| for i in in_: | |
| i = int(i) | |
| if i !=0: | |
| previous *= i | |
| else: | |
| previous += i | |
| print(previous) | |
| ############################################## | |
| ### 34 오답#################################### | |
| ############################################## | |
| # n = int(input()) | |
| # data = list(map(int, input().split())) | |
| n = 7 | |
| data = [12,11,12,15,5,2,4] | |
| dp = [] | |
| for i, j in enumerate(data): | |
| count = 0 | |
| for k in range(i, n): | |
| if j > data[k]: | |
| count += 1 | |
| dp.append(count) | |
| print(dp) | |
| # >> [6, 5, 1, 3, 2, 0, 0] | |
| remain = [] | |
| for j, i in enumerate(dp[:-1]): | |
| if i > dp[j+1]: | |
| remain.append(data[j]) | |
| if min(remain) > data[-1]: | |
| remain.append(data[-1]) | |
| print(remain) | |
| # >> [15, 11, 8, 5, 4] | |
| print(n-len(remain)) | |
| ############################################## | |
| ### 18 ####################################### | |
| ############################################## | |
| def balanced_index(p): | |
| count = 0 | |
| for i in range(len(p)): | |
| if p[i] == '(': | |
| count += 1 | |
| else: | |
| count -= 1 | |
| if count == 0: | |
| return i | |
| # 올바른 쌍? | |
| def check_proper(p): | |
| count = 0 | |
| for i in p: | |
| if i == '()': | |
| count += 1 | |
| else: | |
| if count == 0: # 쌍 안맞음 ()|)) | |
| return False | |
| count -= 1 | |
| return True | |
| def solution(p): | |
| print('=======') | |
| print('p', p) | |
| answer = '' | |
| if p == '': | |
| return answer | |
| index = balanced_index(p) | |
| u = p[:index+1] | |
| v = p[index+1:] | |
| print('u, v', u, v) | |
| # 올바른 -> v에 대해 붙여서 반환 | |
| if check_proper(u): | |
| answer = u + solution(v) | |
| # 올바른X -> | |
| else: | |
| answer = '(' | |
| print(answer) | |
| answer += solution(v) | |
| print(answer) | |
| answer += ')' | |
| print(answer) | |
| u = list(u[1:-1]) | |
| for i in range(len(u)): | |
| if u[i] == '(': | |
| u[i] = ')' | |
| else: | |
| u[i] = '(' | |
| answer += ''.join(u) | |
| print(answer) | |
| print(answer) | |
| return answer | |
| in_ = '())))(((()' | |
| solution(in_) | |
| >>> | |
| ======= | |
| p ())))(((() | |
| u, v () )))(((() | |
| ( | |
| ======= | |
| p )))(((() | |
| u, v )))((( () | |
| ( | |
| ======= | |
| p () | |
| u, v () | |
| ( | |
| ======= | |
| p | |
| ( | |
| () | |
| () | |
| () | |
| (() | |
| (()) | |
| (())(()) | |
| (())(()) | |
| ((())(()) | |
| ((())(())) | |
| ((())(())) | |
| ((())(())) | |
| '((())(()))' | |
| ############################################## | |
| ### 8 ####################################### | |
| ############################################## | |
| in_ = '02984' | |
| in_ = '567' | |
| previous = 1 | |
| for i in in_: | |
| i = int(i) | |
| if i !=0: | |
| previous *= i | |
| else: | |
| previous += i | |
| print(previous) | |
| # 34 | |
| n = int(input()) | |
| data = list(map(int, input().split())) | |
| counter = [] | |
| for i, j in enumerate(data): | |
| count = 0 | |
| for k in range(i, n): | |
| if j > data[k]: | |
| count += 1 | |
| counter.append(count) | |
| remain = [] | |
| for j, i in enumerate(counter[:-1]): | |
| if i > counter[j+1]: | |
| remain.append(data[j]) | |
| if min(remain) > data[-1]: | |
| remain.append(data[-1]) | |
| print(n-len(remain)) | |
| ############################################## | |
| ### 1 ####################################### | |
| ############################################## | |
| def solution(test: list): | |
| test = sorted(test, reverse=True) | |
| j = 1; num_elem = test[0] | |
| while test[num_elem:]: | |
| j+=1 | |
| next_group_start = test[num_elem:][0] | |
| num_elem += next_group_start | |
| # A17 | |
| def init_data(inputs): | |
| # visited = [(i ,j) for j in range(k) for i in range(n)] | |
| mat = inputs[1:-1] | |
| n, k = inputs[0] | |
| s, x, y = inputs[-1] | |
| visited = [] | |
| for i in range(1, n+1): | |
| for j in range(1, k+1): | |
| visited.append((i ,j)) | |
| visited_dict = {i: False for i in visited} | |
| # node | |
| node_dict = {} | |
| iter_ = 1 | |
| for i, ls in enumerate(mat, 1): | |
| for j, elem in enumerate(ls, 1): | |
| if elem != 0: | |
| if elem not in node_dict : | |
| node_dict[elem] = {iter_: []} | |
| visited_dict[(i, j)] = True | |
| node_dict[elem][iter_].append((i, j)) | |
| return visited_dict, node_dict, (s, x, y) | |
| def check_if_answer(cor: tuple, answer: tuple): | |
| if cor == answer: | |
| return True | |
| def check_if_visited(iter_:int, cor: tuple, node: int, visited_dict, node_dict): | |
| if not visited_dict[cor]: | |
| visited_dict[cor] = True | |
| node_dict[node][iter_].append(cor) | |
| return visited_dict, node_dict | |
| # update edge | |
| def update(node_dict, visited_dict, answer, iter_): | |
| fin = False | |
| for node in sorted(node_dict): | |
| node_dict[node][iter_] = [] | |
| for cor in node_dict[node][iter_-1]: | |
| u = max(cor[0]-1, 1); d = min(cor[0]+1, k); r = min(cor[1]+1, n); l = max(cor[1]-1, 1) | |
| for temp in [(u, cor[1]), (d, cor[1]), (cor[0], l), (cor[0], r)]: | |
| if check_if_answer(temp, answer): | |
| fin = True | |
| return node, None, fin | |
| visited_dict, node_dict = check_if_visited(iter_=iter_, cor=temp, node=node, visited_dict=visited_dict, node_dict=node_dict) | |
| return node_dict, visited_dict, fin | |
| for iter_ in range(2, s+1): | |
| node_dict, visited_dict, fin = update(node_dict, visited_dict, question[1:], iter_) | |
| if fin: | |
| print(node_dict) | |
| break | |
| if not fin: | |
| print(0) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment