one Book a Day

물을 먼저 번지게하고 고슴도치를 이동하는 방식으로 한다. 각 이동 단위마다 물을 번지게 해주며 time을 늘려나간다. import sys input = sys.stdin.readline from collections import deque def spread_water(): new_water = [] while water: x, y = water.pop() for dx, dy in delta: nx, ny = x + dx, y + dy if 0

불가능한 경우는 홀수번 나오는 문자가 2개 이상일 경우다. 이 경우를 제외하고 각 문자를 배열에 넣어 정렬 후 뒤집은 배열과 합치는 방법으로 펠린드롬을 만들 수 있다. import sys input = sys.stdin.readline from collections import defaultdict name = input().rstrip() count = defaultdict(int) for char in name: count[char] += 1 char_set = [] flag = 0 mid = '' for char in count: if count[char] % 2: if flag: print("I'm Sorry Hansoo") exit() else: mid = char flag = 1 for _ i..

연구소 2에서 동일하나 마지막에 비활성화 바이러스만 남아있는 경우를 배제해줘야한다. 즉 최소 시간 배열을 만들고 비활성화 바이러스가 있는 영역을 제외한 영역을 차지하는데 걸린 시간을 찾아야한다. import sys input = sys.stdin.readline from collections import deque from itertools import combinations def bfs(q): for x, y in q: visited[x][y] = True times[x][y] = 0 cnt = len(q) while q: for _ in range(len(q)): x, y = q.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0

긴 문자열인 B에 A를 매칭시키며 가장 적은 차이가 답이다. (그 매칭위치에서 좌우 B에 맞춰주면 차이가 더 벌어지지 않음) import sys input = sys.stdin.readline A, B = input().split() # 그냥 B에 A매칭시키면서 차이 가장 작은거 찾아서 출력. min_cnt = float('inf') for i in range(len(B) - len(A) + 1): cnt = 0 for j in range(len(A)): if B[i+j] != A[j]: cnt += 1 min_cnt = min(min_cnt, cnt) print(min_cnt)

처음 풀이는 다음과 같다. 모든 노드에 갔다가 돌아오는 각 합중 max값을 찾는 풀이 그리고 다른 분들의 풀이를 본 결과 역방향 그래프를 그리는 것이 반대로 도착지점에서 현지점까지 오는 거리를 측정할 수 있음을 깨달았다. import sys input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(start): heap = [] visited = {i: float('inf') for i in range(1, N + 1)} visited[start] = 0 heappush(heap, (0, start)) while heap: time, cur_node = heappop(heap) if visited[cur_node] < time..

오랜만에 다익스트라. visited[cur_node] ti..

신장트리에서 마지막 하나의 간선을 그리는 방법으로 트리간 가중치가 존재하지 않기 때문에 간단한 union-find로 풀 수 있다. import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a < b: a, b = b, a parent[b] = a N = int(input()) parent = {i: i for i in range(1, N+1)} for _ in range(N-2): a, b = map(int, input().split()) union(a, b) pi..

set으로 관리. import sys input = sys.stdin.readline delta = ((1, 0), (0, -1), (-1, 0), (0, 1)) N = int(input()) curves = set() for _ in range(N): x, y, d, g = map(int, input().split()) # (x,y)시작, 처음 d방향으로 시작,(처음 선분하나로 시작) g 세대까지 진행.(1개추가, 2개추가, 4개 추가, 8개 추가.. 90도 회전시키며.) curves.add((x, y)) cur_dragon = [d] next_dragon = [d] for _ in range(g+1): for d in cur_dragon: nx, ny = x + delta[d][0], y + delt..

3자리수가 최대라 0, 1, 2자리수까지만 차수 비교해주면 됨. import sys input = sys.stdin.readline N = int(input()) answer = 0 for num in range(1, N + 1): if num < 100: answer += 1 else: digits = list(map(int, str(num))) if digits[0] - digits[1] == digits[1] - digits[2]: answer += 1 print(answer)

자주 나오는 문제. 처음엔 거리 계산해서 안움직이고 풀려했는데 실패. 아래에 안움직이는 코드도 찾아놓음. import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) position = list(map(int, input().split())) q = deque([i for i in range(1, n+1)]) move = 0 for num in position: if q.index(num) < len(q)/2: while q[0] != num: q.rotate(-1) move += 1 else: while q[0] != num: q.rotate(1) move += 1 if q[0] ==..