그리디

1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 크레인의 무게 제한과 박스의 무게를 "crain", "box" 이름으로 ArrayList로 담았다. 그리고 해당 ArrayList들을 모두 내림차순 정렬을 시켰다. ArrayList를 내림차순 정렬을 할 때는 Collection.reverseOrder() 함수를 sort안에 명시해주어야 한다. 정렬된 두 ArrayList의 첫 번째 인덱스 값을 비교한다. 만약 크레인의 첫 번째 값이 박스의 첫 번째 값보다 작을 경우 모든 박스를 담을 수 없기 때..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 설명은 밑에 링크를 타시고 보시면 됩니다. 😶‍🌫️ [Python][백준 2212][정렬][그리디] 센서 - 컴도리돌이 풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 comdolidol-i.tistory.com import java.io.BufferedReader; import java...

풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 추천한다. 🙄 1. 센서 위치를 정렬시킨다. 2. x의 0번째 인덱스부터 n-1 인덱스까지 다음 좌표까지의 거리를 저장한다. 3. 다음 좌표까지의 거리들을 정렬시킨다. 4. 정렬된 좌표 간의 거리 리스트에서 n-k까지 합을 구하여 출력한다. 풀이 코드 n,k,*x = map(int,open(0).read().split()) ;x.sort() print(sum(sorted([x[i+1] - x[i] for i in range(n-1)])[:n-k]))

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 과정 1. 걸리는 일수(t)와 현재 일수(i)의 합이 n을 넘어가면 안되기 때문에 t+i가 n을 넘어가면 현재 일수보다 앞에 있는 일수의 값을 갖고 온다. 2. n을 넘어가지 않으면 현재 일수(i)보다 앞에 있는 일수(i+1)와 i+t 일수에 p를 더한 값과 비교해서 큰 값을 할당해 준다. 풀이 코드 import sys; input = sys.stdin.readline n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] dp = [0] * (n+ 1) for i in range(n-1,-1,-1) : t,p = ar..

1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 풀이 방법 처음에는 아무 생각 없이 dfs로 5분만에 풀었다. 하지만 다음 테스트 케이스에서 바로 다이나믹 프로그래밍을 전환.. 10 1 1 1 1 1 1 1 1 1 1 50 1. n의 값만큼 가격 p를 입력 받고, dp의 크기를 입력 받은 m+1 만큼 할당해준다(음의 값으로). 2.가격 p를 담고 있는 room의 배열의 마지막 인덱스부터 시작하였다. 마지막 인덱스(방번호)에 해당하는 가격이 x라고 정의할 때, 반복문으로 x 부터 m+1 만큼 dp[현재 요금] = m..

코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도..

코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 co..