목록알고리즘/Greedy (3)

공부공간

BOJ - 11047 ) 동전 0

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 동전이 무수히 많고, A(i) 번째는 A(i-1) 번째의 배수이므로 그리디가 성립한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public clas..
알고리즘/Greedy 2022. 3. 5. 10:54
프로그래머스 ) 단속카메라

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 정렬 후, 내가 Cover 할수있는 범위를 좁혀가면서 그 범위를 넘었을 시에 필요한 카메라를 증가시켜주는 그리디문제이다. 사실 우리 머리는 그리디문제를 잘 못풀게 되어있다. import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; class Solution { public int solution(int[][] routes) { int answer = 1; ArrayLis..
알고리즘/Greedy 2020. 8. 17. 14:24
BOJ - 1781 ) 컵라면

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라� www.acmicpc.net 각 데드라인이 정해져있는 문제에서 최대한 많은 컵라면을 받으며 문제를 풀었을때 받을수있는 컵라면의 개수를 구하는 문제이다. 처음 바로생각난것을 정렬+ 그리디인데, 분명 반례가 존재한다는 것을 알고 우선순위큐에 모든 노드를 넣은후 Time을 증가시키면서 Time보다 작은 라면들을 선택하면서 진행해보았다. 첫번째 시도 import java.io.BufferedReader; import java.io.Inpu..
알고리즘/Greedy 2020. 6. 2. 21:21
Prev 1 Next