그리디알고리즘

백준 1931번 : 회의실 배정 (Python)

문제 : www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 처음에는 시작점을 생각하며 어떻게 껴 넣어야 할지 헤멨다. 메인 아이디어는 끝나는 시점이 빨라야 다음 회의가 들어올 수 있으므로 많은 회의가 가능한 것이다. 따라서 종료 시점을 기준으로 코드를 구성해야 한다. meet 리스트에 입력을 받을때 '종료 시간의 인덱스'에 '시작 시간을 원소'로 넣었다. (meet[종료시간].append(시작시간)) 리스트의 길이는 시간을 입력받을때마다 추가해주었다. meet를 하나씩 돌며 시작 시간이 있는지(입력받은 회의가 있는지) 확인한다. 있다면 (len != 0 이라면) 이전에 ..

백준 13305번 : 주유소 (Python)

문제 : www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 한칸씩 이동하며 현재 가장 작은 기름값으로 바로 다음 도로를 지나도록 한다. minoil에 현재 최소 기름값을 넣고 한칸 옮겼을때의 기름값이 더 작으면 minoil을 바꿔서, 더 크면 그대로 두고 바로 다음 길의 길이를 곱하여 결과값에 더한다. 사실상 마지막 주유소는 필요가 없으므로 N-1번만 루프를 돈다. N = int(input()) road = list(map(int,input..