본문 바로가기
반응형

Problem Solving232

[최단 경로] 백준 1238번: 파티 / 골드 3 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import collections import heapq n, m, x = map(int, input().split()) graph = collections.defaultdict(list) for i in range(m): u,v,w = map(int, input().split()) graph[u].append([v,w]) # go back to home start .. 2021. 6. 7.
[구현 문제] 백준 3190번: 뱀 / 골드 5 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net import collections n = int(input()) k = int(input()) apples = collections.defaultdict(int) for i in range(k): x, y = map(int, input().split()) x -= 1 y -= 1 apples[1000*x+y] = 1 t = int(input()) turns = {} for i in range(t): a,.. 2021. 6. 7.
[구현 문제] 백준 15686번: 치킨 배달 / 골드 5 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net import itertools import sys n, m = map(int, input().split()) graph = [] house = [] shop = [] for i in range(n): row = list(map(int, input().split())) for j in range(n): if row[j] == 1: house.append([i, j]) elif .. 2021. 6. 7.
[그리디] 백준 2812번: 크게 만들기 / 골드 5 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net import sys n, k = map(int, input().split()) lst = input() target = n-k answer = "" pick = 0 i = 0 while pick < target: maxnum = -sys.maxsize maxidx = None find = False for j in range(i, pick + k + 1): if lst[j] == '9': answer +='9' pick +=1 i = j +1 find = True break.. 2021. 6. 3.
[그리디] 백준 11000번: 강의실 배정 / 골드5 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 아이디어를 떠올리기 힘들다. 우선순위 큐를 생각하면 실마리를 찾을 수 있다. import heapq n = int(input()) lst = [] for i in range(n): lst.append([x for x in map(int,input().split())]) q= [] lst.sort(reverse=True) answer = 0 count = 0 while lst: cls = lst.pop() start, finish = cls[0].. 2021. 6. 2.
[최단 경로] 백준 11657번: 타임머신 / 골드 4** https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 아직은 생소한 벨만-포드 알고리즘이 필요한 문제다. 벨만-포드 알고리즘과 다익스트라의 차이점은 벨만-포드는 음수 가중치가 있는 경우에도 최단 경로를 찾을 수 있다. 공통점은 시작 노드를 특정하고 그 노드에서 다른 노드까지의 거리를 구한다는 것이다. 원리 자체는 플로이드-워셜과 비슷하다는 느낌을 받았다. 다만 벨만-포드는 음수 사이클에 빠.. 2021. 6. 2.
반응형

티스토리툴바