ALGORITHM/백준67 [BOJ/PYTHON] 11657. 타임머신 (최단 경로 - 벨만포드) 백준 문제 링크: https://www.acmicpc.net/problem/11657 문제 요약 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하기 이동시간이 양수면 그만큼 이동, 0이면 순간이동, 음수면 타임머신으로 시간 되돌아감 핵심 아이디어 시작점, 도착점, 시간이 주어졌기에 정점과 간선의 가중치가 주어진 상황이다. 근데 이 시간이 음수 값도 가능하기에 다익스트라로 풀 수 없다. 벨만포드로 풀면 된다. 풀이 # gold4-11657. 타임머신 import sys input = sys.stdin.readline n, m = map(int, input().split()) # 도시 개수, 버스 노선 개수 edges = [] for _ in range(m): a, b, c = map(int.. 2023. 5. 16. [BOJ/PYTHON] 18223. 민준이와 마산 그리고 건우 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/18223 문제 요약 마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력 핵심 아이디어 그래프 간선에 가중치가 있고, 가중치가 양수이기 때문에 다익스트라 알고리즘을 사용하면 된다. 이때, 건우를 구해준 후 마저 마산까지 가는 거리가 최단경로보다 길어지지 않으면 건우를 구하는 거라 건우를 구하러까지 가는 최단 거리, 구하고 나서 마산까지 가는 최단 거리, 출발지에서 마산까지 직통으로 가는 최단 거리값들이 필요하다. 풀이 # gold4-18223. 민준이와 마산 그리고 건우 impor.. 2023. 5. 16. [BOJ/PYTHON] 20921. 그렇고 그런 사이 # silver2-20921. 그렇고 그런 사이 import sys put = sys.stdin.readline # 왼쪽 수가 오른쪽보다 큰 경우(그렇고 그런 사이)가 k가지여야 함 n, k = map(int, put().split()) # n명, k개의 경우 만들기 answer = [] visited = [0] * (n+1) maxN = n # 첫 번째 사람한테 n번(제일 높은 값) 쪽지 주면 n-1만큼 생김 while k: if maxN - 1 그다음 제일 큰 수로 갱신 # (if문 x) 생길 수를 1 줄여서 다시 도전 maxN -= 1 for i in range(1, n+1): if not visited[i]: answer.append(i) # 낮은 수부터 순차적 배치 print(' '.join(m.. 2022. 3. 27. [BOJ/PYTHON] 11399. ATM # silver3-11399. ATM import sys put = sys.stdin.readline # 각 사람의 인출 시간 = 앞 사람의 인출 시간을 대기하는 시간 + 본인의 인출 시간 # 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값? num = int(put()) arr = list(map(int, put().split())) result=0 arr.sort() # 앞사람이 계속 더해져서 소요 시간 짧은 사람이 앞에 와야 전체 인출 시간이 짧아짐 for i in range(num): result += arr[i]*(num-i) # arr[i]의 시간동안 i 뒤의 (num-i)명이 기다림 print(result) 2022. 3. 27. [BOJ/PYTHON] 13305. 주유소 # silver4-13305. 주유소 import sys put = sys.stdin.readline # 각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산 n = int(put()) #도시 개수 length = list(map(int, put().split())) #도로의 길이 price = list(map(int, put().split())) #도시의 리터당 가격 # (i-1)번째에서 i번째 도시로 가는 거리에 소모되는 기름은 # 1~(i-1)번째 주유소 중 가장 가격이 싼 도시의 주유소 고르면 됨 sum = 0 minPrice = price[0] for i in range(n-1): if minP.. 2022. 3. 27. [BOJ/PYTHON] 23559. 밥 # gold5-23559. 밥 import sys put = sys.stdin.readline # 5,000원짜리 메뉴의 맛 A와 1,000원짜리 메뉴의 맛 B 중 예산 안에 맛의 합을 극대화 n, x = map(int, put().split()) taste = [list(map(int, put().split())) for _ in range(n)] # 예산 제약 존재, 1000원이 더 맛있는 경우도 존재.. # 맛 수치가 높은 순으로 정렬해 예산 안에서 최적 선택하기 # 맛 수치는 그날의 비교우위. 50 30인 날보다 50 20인 날 5천원짜리 먹는 게 이득 # 일단 천원짜리 다 고른다고 해놓고 예산이 허용되는 한 만족도 높은 순서대로 5천원짜리 껴넣기 # 5천에서 천원짜리 만족도를 뺀 거를 내림차순 .. 2022. 3. 27. 이전 1 ··· 8 9 10 11 12 다음