one Book a Day

dp[층수][둘사이 거리]의 경우의 수로 계산. 거리가 그대로일 경우 둘(아래아래, 대각,대각) 거리가 줄경우 하나(대각아래) 거리가 늘경우 하나(아래대각) 거리가 0인경우는 그냥 배제 import sys input = sys.stdin.readline n = int(input()) dp = [[0]*(n+1) for _ in range(n+1)] dp[2][1] = 2 for i in range(3,n+1): for j in range(1,i): dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-1] + dp[i-1][j+1])%10007 sum_n = 0 for i in range(1,n): sum_n += dp[n][i] print(sum_n%10007)

요새 파싱문제가 많이나오면서 자릿수를 맞춰서 출력해야 하는 문제도 종종 나오는 것 같다. 1. zfill(width) "2".zfill(4) >>> 0002 0 으로 채워준다. 2.rjust(width[,fillchar]) "123",rjust(5,"a") >>> aa123 원하는 문자열로 채워준다

조건 검사는 큰것부터 import sys input = sys.stdin.readline s = input().rstrip() n = len(s) idx = 0 cnt = 0 dict_c = ['c=','c-','z=','d-','lj','nj','s=','z='] while idx < n : if idx+2 < n and s[idx:idx+3]=='dz=': idx += 3 cnt += 1 continue if idx+1 < n: check = s[idx:idx+2] if check in dict_c: idx += 2 cnt += 1 continue idx += 1 cnt += 1 print(cnt)

처음에 dfs하려다 숫자 처리하기 귀찮아서 그냥 단계별로 파싱함. eval쓸수있었으면 4줄로 끝나는데 0으로 시작하는 숫자있어서 int처리 해줘야함. import sys input = sys.stdin.readline # eval쓸라그랬는데 0으로 시작하는 숫자있어서 실패.. expression = input().split('-') new_expression = [] for ex in expression: nums = ex.split('+') sum_n = 0 for num in nums: sum_n += int(num) new_expression.append(sum_n) print(2*new_expression[0] - sum(new_expression))

대놓고 플로이드 워셜이라 풀었는데 카테고리는 bfs.. bfs로 풀수있나? import sys input = sys.stdin.readline # 플로이드 워셜 탐색 N, M = map(int, input().split()) graph = [[float('inf') for _ in range(N+1)] for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 for k in range(1,N+1): graph[k][k] = 0 for i in range(1,N+1): for j in range(1,N+1): if graph[i][j] > graph[i][k] + graph[k..

그냥 돌리면서 경로 담아주면되됨 import sys input = sys.stdin.readline from collections import defaultdict def DFS(v): path.append(v) check[v] = True for i in graph[v]: if check[i]==False: DFS(i) def BFS(v): queue = [v] path.append(v) check[v] = True while queue: v = queue.pop(0) for i in graph[v]: if check[i] ==False: queue.append(i) path.append(i) check[i] = True N,M,V = list(map(int,input().split())) graph ..

set정렬후 이분탐색. 그냥 정렬로도 풀수있나? import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) arr = list(map(int, input().split())) arr2 = sorted(list(set(arr))) for num in arr: print(bisect_left(arr2,num),end=' ')

dfs or bfs or disjoint-set 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 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,N+1)} for ..

가중치 기준 내림차순 정렬하고 마지막날부터 거꾸로 먹는다. import sys input = sys.stdin.readline N, T = map(int, input().split()) w_ps = [list(map(int, input().split())) for _ in range(N)] w_ps.sort(key = lambda x: x[1],reverse=True) answer = 0 for w, p in w_ps: answer += (w + p*(T-1)) T -= 1 print(answer)

다익스트라로 찾습니다. 최소거리는 늘 다익스트라 import sys input = sys.stdin.readline from collections import deque def dijkstra(start): queue = deque() queue.append([0,start]) visited = {i: float('inf') for i in range(1,N+1)} visited[start] = 0 while queue: cur_dist,cur_node = queue.popleft() for next in graph[cur_node]: if visited[next] > cur_dist+1: visited[next] = cur_dist+1 queue.append([visited[next], next]) r..