https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 음수간선이 포함되었기에 벨만 포드 알고리즘을 사용한다. 만일 n번의 시도에서도 최단경로간 갱신된다면 음수간선이 존재한다. # 1865번 웜홀 import sys input = sys.stdin.readline INF = int(1e9) def bf(): distance = [INF] * (n+1) # 시작 노드에 대해서 초기화 distance[1] = 0 # 전체 n번의 라운드(..

https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 풀이 2차원배열로 구현한 도화지 위에 색칠을 해준 뒤 색이 칠해진 칸을 전부 다 더해주면 답이 나온다. # 2653번 색종이 n = int(input()) # 도화지 구현 graph = [[0]*101 for _ in range(101)] for _ in range(n): a, b = map(int, input().split()) for i in range(a, a+10): for j in range(b, ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 sort에 관련된 블로그 글 참고 # 1931번 회의실 배정 # 1, 가장 빨리 끝나는 강의 우선으로 정렬 2, 가장빨리 시작하는 강의로 정렬 import sys input = sys.stdin.readline n = int(input()) arr = [] for _ in range(n): a, b = map(int, input().split()) arr.append((a, b)) arr.sort(key = lambda x:(x[1],x[0])) cnt = 0 end = 0 for s, t in arr: i..

https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 풀이 진짜약수로 주어진 숫자의 가장 작은 숫자와 가장 큰 숫자를 곱해준다면 구하고자하는 답이 나올것이다.가장 큰수와 2를 곱해주면 안된다. 21같은 숫자는 진짜 약수가 3, 7인데 2를 14가 구하고자하는 답이 아니기 때문이다. # 1037번 약수 import sys input = sys.stdin.readline _ = input().rstrip() arr = list(map(int, i..

https://www.acmicpc.net/problem/2980 2980번: 도로와 신호등 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔 www.acmicpc.net 풀이 단순하게 구현만 해주면 되는 문제이다. 문제의 답은 걸리는 시간이다. 도로의 위치를 저장할 변수와 시간을 저장할 변수를 나누어서 생각해주어야한다. # 2980번 도로와 신호등 import sys input = sys.stdin.readline cur_dis = 0 ans = 0 n, l = map(int, input().split()) for _ in range(n): d, r, g = map(i..

https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 풀이 입력으로 5개의 단어가 주어진다. 단어들의 길이는 15글자를 넘지않기에 리스트를 작성해서 이중for문으로 출력해준다. # 10798번 세로읽기 import sys input = sys.stdin.readline graph = [[False]*15 for _ in range(5)] for i in range(5): word = list(input().rstrip()) for j in r..

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 풀이 1, 단방향문제 최대값이 문제없어서 INF는 10억을 잡아주었다. 2, 각 경우의 수의 distance를 받아서 마을 ->파티 경로랑 파티 -> 마을 경로를 더해서 비교해준다. 마무리만 잘해주면 된다. # 1238번 파티 import sys import heapq input = sys.stdin.readline INF = int(1e9) def dijkstra(..

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 풀이 음수의 간선이 포함되었기에 벨만 포드 알고리즘으로 문제를 풀어준다. 벨만포드의 알고리즘은 다익스트라 알고리즘의 최적의 해를 포함한다. 다만 시간복잡도가 다익스트라에 비해 높다.자세한 내용은 https://sunghyun98.tistory.com/51 이 글에서 확인 할 수 있다. # 11657번 타임머신 # 벨만 포드 알고리즘 im..