본문 바로가기
728x90

코딩테스트/그리디4

[python] 백준 11399번: ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys #sys.stdin = open('input8.txt','r') input = sys.stdin.readline n = int(input()) p = list(map(int,input().split())) p.sort() answer = 0 for i in range(1,len(p)+1): # 총 p만큼의 사람이 기다림 for j in rang.. 2023. 1. 30.
[python] 백준 11047번: 동전 0 https://www.acmicpc.net/user/gurwns876 gurwns876 정보 시도했지만 맞지 못한 문제 www.acmicpc.net 동전 거스름 돈 문제는 그리디 알고리즘에서 유명한 문제이다. 1. 문제 해석 1) 각 동전이 다음 동전이 될 때 n의 배수이므로 큰 숫자부터 차례대로 나누면 된다. 2) 이때 총합 k를 구할 때 동전의 갯수를 구하면 된다. 2. 풀이 1. 동전이 n의 배수이므로 그리디 알고리즘을 사용하면 된다. 2. 처음부터 큰 숫자를 나눈 다음, 몫을 answer에 더하고 나머지를 k에 다시 대입하여 해결한다. (동전의 n의 배수가 아닐 때는 그리디 알고리즘을 사용하면 안된다. 이 문제도 추후에 풀어보자) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1.. 2023. 1. 28.
그리디 문제 모음 그리디 문제 그리디 문제를 풀 때 간단하게 생각했었다. 그러나 실제로 코딩테스트를 칠 때 생각과 달리 구현과정에서 까다롭게 느껴지는 문제들이 많았다. 그래서 이 참에 한번에 정리해서 풀어 보려고 한다. 11047번 동전 0 https://www.acmicpc.net/problem/11047 1012번 유기농 배추 https://www.acmicpc.net/problem/1012 ATM 11399 https://www.acmicpc.net/problem/11399 로프 2217 https://www.acmicpc.net/problem/2217 2583 영역구하기 https://www.acmicpc.net/problem/2583 11000 강의실배정 https://www.acmicpc.net/problem/.. 2023. 1. 26.
<PART 2> 그리디 예제 큰 수의 법칙 n,m,k가 있습니다. n은 배열의 원소 갯수, m은 더하는 횟수, k는 연속한 수가 k번 초과할 수 없음을 의미합니다. 이를 가지고 원소들을 더해서 가장 큰수를 만드는 것이 목적입니다. ex) n=5이면 2,4,5,4,6로 원소 5개를 주고 m=8, k=3이라면 6+6+6+5+6+6+6+5 =46이 됩니다. 입력예시 5 8 6 2 4 5 4 6 출력 예시 46 1 2 3 4 5 6 7 8 9 10 11 12 N, M, K = map(int,input().split()) a = sorted(list(map(int,input().split()))) cnt = 0 a_sum = 0 for i in range(M): if cnt == K: #k초과지만 cnt가 k가 되면 이미 k수만큼.. 2022. 9. 28.
728x90

티스토리툴바