Algorithm/Greedy4 주유소 백준 13305번https://www.acmicpc.net/problem/13305 처음 풀이array1 = [2, 3, 1]array2 = [5, 2, 4, 1]배열에서 마지막 원소를 제외하고 가장 값이 작은 원소를 구한다min(array2[:-1])결과는 22[0]은 2가 아니다array1[0] * array2[0]한 결과를 비용에 저장 10을 저장2[1]은 2이다현재 index의 원소에서 마지막 원소까지의 합을 구한다sum(1[1:]) = 4이를 최소값과 곱한 결과를 비용에 더함2 * 4 = 810 + 8 = 18최소 비용 = 18 리터당 가격의 최솟값을 찾아 이후 거리를 모두 최솟값으로 계산하려는 방식으로 이는 최적의 솔루션이 아니다매 순간 현재까지의 최저 가격으로 기름을 채우면서 이동해야 한다.. 2024. 10. 17. 회의실 배정 백준 1931번 회의실 배정https://www.acmicpc.net/problem/1931 각 회의마다 회의가 시작하는 시간, 끝나는 시간이 주어지는데끝나는 시간이 빠를 수록 가능한 많은 회의를 할 수 있다 따라서 sort의 key로 튜플을 줄 때튜플의 첫 번째 원소를 회의가 끝나는 시간, 두 번째 원소를 회의가 시작하는 시간으로 했다 N = int(input().strip())classList = []startTime = 0count = 0for _ in range(N): # st, et = map(int, input().split()) classList.append(list(map(int, input().split())))classList.sort(key = lambda i : (i[1].. 2024. 10. 15. 동전 0 백준 11047번 동전 0https://www.acmicpc.net/problem/11047 동전을 값이 작은 순으로 입력 받아 coinList에 추가이후 reverse를 통해 내림차순으로 정렬for문을 돌며 원소 하나씩 K // 해당 원소 했을 때 몫이 1 이상이라면 count에 몫을 추가하고K 값을 K % 해당 원소 값으로 갱신했다 K가 0이 되면 K // 해당 원소 계산에서 몫이 1 이상이 될 일이 없으니 따로 처리하지 않았는데K가 0일 때 break 하는 if문을 추가했다면 더 효율적이었을 것이다 import sysinput = sys.stdin.readlineN, K = int(input().split())coinList = []count = 0for _ in range(N): coin =.. 2024. 10. 14. 공주님의 정원 백준 2457번 공주님의 정원https://www.acmicpc.net/problem/2457 개화 날짜와 낙화 날짜가 주어지는데, changeDate 함수를 만들어서 날짜를 네 자릿수 숫자로 만들었다 start 변수를 이용해서 start 변수보다 개화 날짜가 빠른 원소 중 제일 늦게 낙화되는 원소를 고른다 while문 내의 while문은 최대 n번을 돈다앞서 flowers 리스트를 sort한데다 start 날짜보다 개화 날짜가 빠르거나 같다는 조건이 있으니 같은 원소를 다시 방문할 필요가 없다 import sysinput = sys.stdin.readlinedef changeDate(month, day): return month * 100 + dayn = int(input().strip())flo.. 2024. 10. 4. 이전 1 다음