반응형 Python9 백준 BOJ 1976번 여행 가자 골드5 - Python 풀이 https://www.acmicpc.net/problem/1976 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시.. 2023. 10. 20. 백준 2096번 내려가기 골드5 - Python 풀이 다이나믹 프로그래밍을 활용하는 문제이다. 메모리 제한에 대한 생각 없이 단순히 메모이제이션에 대한 아이디어만 가지고 문제를 풀면 다음과 같은 풀이를 생각할 수 있다. import sys, copy input = sys.stdin.readline n = int(input()) dp_max = [list(map(int, input().split())) for _ in range(n)] dp_min = copy.deepcopy(dp_max) for i in range(1, n): # 0 dp_max[i][0] += max(dp_max[i - 1][0], dp_max[i - 1][1]) dp_min[i][0] += min(dp_min[i - 1][0], dp_min[i - 1][1]) # 1 dp_max[i][.. 2023. 10. 18. 백준 11000번 강의실 배정 골드5 - Python 풀이 문제를 보자마자 직관적으로 이런 풀이를 떠올릴 수 있는데, 수업 시간표를 딕셔너리로 생성하고, 각 시간대 중 배정된 강의 수의 최대 값이 필요한 강의실의 개수일 것이다. import collections n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] time_table = collections.defaultdict(int) for s, t in arr: for i in range(s, t): time_table[i] += 1 print(max(time_table.values())) 그러나 위 풀이는 메모리 초과가 발생한다. 어짜피 겹치는 시간대만 확인하면 되므로, 시간대를 정렬해서 계산하면 한번만 순회하여 구할 수 있.. 2023. 10. 12. 이전 1 2 다음 반응형