느낌표 공장

풀이 1 처음부터 탐색 n, k, b = map(int, input().split()) # n번까지의 번호가 붙은 횡단보도, k개의 신호등, 부서진 신호등 개수 b lights = [0 for _ in range(n+1)] # 신호등 표시 for _ in range(b): lights[int(input())] = 1 # 부서진 신호등 1로 표시 l = 0 answer = float('inf') # 최소 수리해야하는 신호등 개수 tmp = 0 # 수리해야하는 신호등 개수 임시로 담는 변수 for i in range(1, n+1): if lights[i]: # 부서진 신호등이라면 + 1 tmp += 1 if i - l == k: # k 개수 충족됐다면 if tmp < answer: # 고칠 신호등 개수 최소..

import heapq # 방향 벡터 dy = [1, -1, 0, 0] dx = [0, 0, 1, -1] def dijkstra(): queue = [[rupee[0][0], 0, 0]] # 탐험 할 곳 담아둘 리스트 # 시작지점 루피, y좌표, x좌표 넣기 visited[0][0] = rupee[0][0] # 시작지점 루피 while queue: d, y, x = heapq.heappop(queue) # 현재까지 잃은 루피, 현재 좌표 꺼내기 if y == n-1 and x == n-1: # 동굴 출구까지 왔다면 현재까지 잃은 루피 출력 print(f'Problem {tc}: {d}') return if visited[y][x] < d: # 현재까지 잃은 루피가 저장되어 있는 루피보다 크다면 패스 co..

def dfs(cnt): # cnt => 행 global answer if cnt == n: # 모든 체스를 다 두었다면 answer += 1 return for i in range(n): if visited[i]: # 해당 열에 체스 이미 있다면 패스 continue idx[cnt] = i # 없으면 해당 열에 체스 놓기 for j in range(cnt): # 대각선 체크 # 대각선의 경우 두 좌표에서 행 - 행 = 열 - 열이 같으면 두개는 같은 대각선상에 있다 if (idx[cnt] - cnt) == (idx[j] - j) or (idx[cnt] + cnt) == (idx[j] + j): break else: visited[i] = True # 현재 열 방문처리 dfs(cnt + 1) # 다음 행..

n = int(input()) # 도시의 수 n cost = [list(map(int, input().split())) for _ in range(n)] # 비용 행렬 dp = [[1e9 for _ in range(1

n = int(input()) # 사람과 일의 수 n d = [list(map(int, input().split())) for _ in range(n)] # 각 사람(행)마다의 일(열) dp = [[1e9 for _ in range(1

h, w = map(int, input().split()) # 세로 길이 h, 가로 길이 w blocks_h = list(map(int, input().split())) # 블록의 높이들 l = 0 # 왼쪽 포인터 r = w-1 # 오른쪽 포인터 max_l = max_r = 0 # 왼쪽, 오른쪽의 각 블록의 최대 높이를 저장할 변수 rainwater = 0 # 고이는 빗물의 총량 while l < r: # 각 블록의 최대 높이 갱신 max_l = max(max_l, blocks_h[l]) max_r = max(max_r, blocks_h[r]) if max_l < max_r: # 오른쪽 블럭이 더 큰 경우 rainwater += max_l - blocks_h[l] # 왼쪽 블럭을 기준으로 빗물 계산 l ..

n = int(input()) # 풍선의 개수 papers = list(enumerate(map(int, input().split()))) # 풍선 안의 종이에 적혀 있는 수 p = 1 # 터트릴 지점을 가르키는 포인터 move = 0 # while n: p += move # 포인터 움직이기 # 포인터 인덱스에 맞추기 if move < 0: # 음수일때 p %= n else: # 양수일때 p = (p - 1) % n # 터진 풍선 고려해서 -1 해주기 idx, move = papers.pop(p) # 풍선 터뜨리기 (풍선 위치, 터진 풍선에 들어있는 종이) n -= 1 # 풍선개수 -1 print(idx + 1, end=' ') # 터진 풍선 위치 출력 포인터를 움직이는 방식으로 문제를 해결했다 ! * ..

seq1 = input() # 문자열 1 seq2 = input() # 문자열 2 seq1_l = len(seq1) + 1 # 각 문자열의 길이 seq2_l = len(seq2) + 1 dp = [["" for _ in range(seq2_l)] for _ in range(seq1_l)] # LCS를 저장할 DP for i in range(1, seq1_l): for j in range(1, seq2_l): if seq1[i-1] == seq2[j-1]: # 방금 막 추가한 문자가 같다면 dp[i][j] = dp[i-1][j-1] + seq1[i-1] # 기존 문자열 + 방금 문자 else: # 같지 않다면 if len(dp[i-1][j]) < len(dp[i][j-1]): # 현재 dp의 좌측과 위의 ..

m = int(sys.stdin.readline()) # 수행해야 하는 연산의 수 s = 0 # 비어있는 공집합 s for i in range(m): command = sys.stdin.readline().split() if command[0] == 'all': # S를 {1, 2, ..., 20} 으로 바꾼다. s = (1

import heapq def dijkstra(s, e): dist = [float('inf') for _ in range(n+1)] # 경로 시간 초기화 queue = [] heapq.heappush(queue, [0, s]) # 시작 지점 넣어주기 dist[s] = 0 # 시작지점의 길이 0으로 설정 (시작 -> 시작 의 시간은 0) while queue: d, now = heapq.heappop(queue) # 현재까지의 시간과 현재 마을 꺼내기 if now == e: # 도착지점이면 시작 -> 현재 마을까지 최단 거리 return return d # 학생 마을 -> x 로 갈때만 해당 if dist[now] < d: # 현재 마을까지 걸리는 저장된 시간보다 꺼낸 시간이 더 크다면 pass cont..