느낌표 공장

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이과정 컴퓨터와 시간을 주고 최소 시간으로 모든 컴퓨터를 연결해야 한다. 그리고 연결하는 횟수와 연결할 컴퓨터의 번호를 출력하는 문제이다. 따라서 노드와 거리(시간)이 있고 최단 거리 찾기라고 생각하여 다익스트라 알고리즘을 활용하여 풀었다. 처음에는 for문으로 dijkstra 함수를 모든 컴퓨터에서 시작시켜서 거기서 가장 시간이 적게 드는 곳을 연결해야지 라고 ..

words = input() # 입력받은 문자열 explode = list(input()) # 폭발 문자열 exp_l = len(explode) new_words = [] for word in words: new_words.append(word) # 기존 문자열의 단어 하나를 새 리스트에 추가 # new_words의 마지막 글자가 폭발 문자열의 마지막 글자와 같고, # 그래서 끝의 글자들이 폭발 문자열과 같다면 if new_words[-1] == explode[-1] and new_words[-exp_l:] == explode: for _ in range(exp_l): # 폭발 시키기 (문자 제거) new_words.pop() if new_words: # 문자 남아있다면 문자열로 변환하여 print pr..

n = int(input()) # 단어의 개수 words = [[] for _ in range(8)] # 단어를 자리 수별로 저장할 리스트 word_dic = {} # 단어 값을 넣을 딕셔너리 for i in range(n): word = input() # 단어 입력받기 len_word = len(word) for j in range(len_word): words[7-j].append(word[len_word-j-1]) # words에 자리 별로 단어 넣어주기 word_dic[word[j]] = word_dic.get(word[j], 0) + 10 ** (len_word-j-1) # 해당 자리에 맞는 값 넣기 numbers = [] for num in word_dic.values(): # 알파벳 빼고 값..

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

n = int(input()) # 도시의 수 cost = [list(map(int, input().split())) for _ in range(n)] # 비용 행렬 visited = [False for _ in range(n)] # 도시 방문 리스트 (모든 도시를 방문해야 함) answer = 1e9 # 최소 비용이므로 정답 크게크게 def dfs(s, now, total): global answer if answer < total: # 가지치기 return # 이미 비용이 기존에 저장한 순회 경로 비용보다 커졌다면 돌아가 if s == now and False not in visited: # 모든 도시를 방문했고, 시작지점으로 돌아왔다면 if total < answer: # 최소 비용으로 갱신 answ..

import heapq def dijkstra(): dist = [float('inf') for _ in range(n+1)] # 가중치 초기화 queue = [[0, a]] # 횟수, 시작 문자 넣기 dist[a] = 0 # 시작지점 가중치 0 while queue: d, now = heapq.heappop(queue) # 현재까지 치환 횟수, 현재 문자 뽑기 if now == b: # 바꾸려고 하는 문자 b라면 print(d) # 현재까지 치환 횟수 출력 return if dist[now] < d: # 저장한 치환횟수보다 꺼낸게 더 크다면 패스 continue for next in visited[now]: # 현재 문자에서 바꿀 수 있는 문자로 가보기 nd = d + 1 # 치환 횟수 + 1 if n..

처음 풀이 n = int(input()) numbers = list(enumerate(map(int, input().split()))) # (인덱스, 숫자) 같이 저장 numbers.sort(key=lambda x: x[1]) # 숫자 기준으로 정렬 is_even = True # 홀수 순서, 짝수 순서 판별 for idx, num in numbers: if (idx % 2 and is_even) or (not idx % 2 and not is_even): # 인덱스가 홀수인데 짝수 순서이거나, 인덱스가 짝수인데 홀수 순서라면 print('NO') # 정렬 불가능 break is_even = not is_even else: print('YES') 위의 풀이는 (인덱스, 숫자)를 같이 저장하고 정렬해서 해당..

풀이 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) # 다음 행..