Algorithm(알고리즘)131 백준 11047번 파이썬 풀이 | 동전 0 | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 이 문제도 Greedy(그리디)로 풀 수 있다. 동전 거스름돈과 비슷하다고 생각하면 쉽다. 먼저 K보다 같거나 클때 break 시키고 그때 index i 부터 -1씩 진행하면서 몫(//) 을 더해주고 K를 계속 나머지(%)로 나눠준다. 2020. 6. 29. 백준 1541번 파이썬 풀이 | 잃어버린 괄호 | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제의 핵심은 '-' 부호를 split 하여서 괄호로 묶어주면 된다. 예를 들어서 55 - 50 +40 -10 +5 의 최소값은 55 - (50 + 40) - (10 +5) = -50 이다. String으로 받아주기 때문에 '-'로 나누고 '-'에 있는 것들을 '+'로 나눠서 더해준다. 2020. 6. 29. 백준 11399번 파이썬 풀이 | ATM | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net Sort를 한 후에 [0:i+1]까지를 계속 더해가는것이 핵심이다. 이전까지 걸린 시간을 계속해서 더하는 것이므로 1 , 1+2 , 1+2+3, 1+2+3+3, 1+2+3+3+4 를 하면 된다. 2020. 6. 28. 백준 5585번 파이썬 풀이 | 거스름돈 | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건� www.acmicpc.net 그리디(Greedy) 알고리즘은 그 순간 최적의 선택을 하는 알고리즘이다. 그 중 가장 기본적인 예시로 동전 거스름돈이 많이 사용된다. 여기서 주의할 점은 파이썬에서는 / 는 소수점까지 나타내므로 // 를 해서 소숫점을 제거해야 한다. 2020. 6. 28. 이전 1 ··· 26 27 28 29 30 31 32 33 다음
