one Book a Day

크루스칼 import sys input = sys.stdin.readline from heapq import heappop,heappush 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 level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] += 1 else: parent[a] = b n, m = map(int, input().split()) parent = {i:i for i in range(1,n+1)} level = {i: 0 for i in range(1..

뒤에 2개는 상태인자. 방향전환 가능여부와 바라보는방향 import sys input = sys.stdin.readline # 남북 w 동서도로 h개 # 남북방향 도로는 왼쪽부터 1,2,...w개 동서도로는 아래부터 1,2,.,..h개 # 서쪽 i번째에서 남북 남쪽j번째도로가 만나는 교차로는 i,j이다. # (1,1) (w,h) 가는방법. 방향전환은 최소2칸이상. # 상태값(x과표, y좌표, x방향전환가능, y방향전환 가능) w,h = map(int,input().split()) dp = [[[[0 for _ in range(2)] for _ in range(2)] for _ in range(101)] for _ in range(101)] # 앞의 0,1은 방향전환이 가능하냐, 불가능하냐? 뒤의 0,1은..

import sys input = sys.stdin.readline dp = [1,1,2,2,3,3] for i in range(6,100001): dp.append((dp[i-2]+dp[i-4]+dp[i-6])%1000000009) for _ in range(int(input())): n = int(input()) print(dp[n])

pkai 만 조심하면된다. print('YES' if not input().replace('pi',' ').replace('ka',' ').replace('chu',' ').strip() else 'NO')

그냥 bfs 2번. 100*100이라 시간은 넉넉했다. import sys input = sys.stdin.readline from collections import deque def bfs(x,y,color): visited[x][y] = True q = deque() q.append([x,y]) while q: x,y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

간단한 dp문제. 규칙이 보인다. for _ in range(int(input())): n = int(input()) dp = [1,1,1,2,2] if n>5: for i in range(5,n): dp.append(dp[i-1]+dp[i-5]) print(dp[n-1])

모든 조합의 경우의 수는 (각 종의 수+1(안 입거나 무언갈 입거나의 경우의 수)) 의 곱 -1(아무것도 안 입는 경우의 수) import sys input = sys.stdin.readline from collections import defaultdict for _ in range(int(input())): n = int(input()) clothes = defaultdict(int) ans = 1 for _ in range(n): name, type_c = input().split() clothes[type_c] += 1 for cloth in clothes: ans *= clothes[cloth]+1 print(ans-1)

대놓고 bfs import sys input = sys.stdin.readline from collections import deque def bfs(start): visited[start] = True q = deque() q.append([start,'']) while q: cur_register, commands = q.popleft() if cur_register==target: return commands for command in 'DSLR': if command=='D': next_register = (cur_register*2)%10000 elif command=='S': next_register = (cur_register-1)%10000 elif command=='L': next_reg..

3차원 6방 탐색으로 바뀐 토마토 import sys input = sys.stdin.readline from collections import deque def bfs(red_tomatoes, tomato_cnt): day = -1 while red_tomatoes: n = len(red_tomatoes) for _ in range(n): x,y,z = red_tomatoes.popleft() for dx,dy,dz in d: nx = x + dx ny = y + dy nz = z + dz if 0

cnt >= N 조건 안넣어서 좀 걸 import sys input = sys.stdin.readline N = int(input()) M = int(input()) S = input().rstrip().replace('IO','*') + 'F' flag = 0 cnt = 0 ans = 0 for char in S: if flag: if char=='*': cnt += 1 else: if cnt >= N: if char=='I': ans += 1 ans += cnt - N cnt = 0 flag = 0 else: if char=='*': flag = 1 cnt += 1 print(ans)