[BOJ/Greedy] 백준 1026 - 보물 (Java)
·
💻/코딩테스트
1026 - 보물https://www.acmicpc.net/problem/1026문제길이가 N인 정수 배열 A, B$S = A[0] * B[0] + \dots + A[N-1] * B[N-1]$S의 값을 가장 작게 만들기 위해 A의 수를 재배열(단, B에 있는 수는 재배열 X)=> S의 최솟값을 출력입력첫째 줄: N둘째 줄: A에 있는 N개의 수 순서대로 주어짐셋째 줄: B에 있는 수가 순서대로 주어짐N (자연수) 출력: S의 최솟값풀이`Arrays.sort(A)`A: 오름차순 정렬`Arrays.sort(B, Collections.reverseOrder())` B: 내림차순 정렬예시A = [1, 1, 1, 6, 0]B = [2, 7, 8, 3, 1] -> A = [1, 1, 0, 1, 6]과 같이 재배열하..
[BOJ/Greedy] 백준 2217 - 로프 (Java)
·
💻/코딩테스트
2217 - 로프https://www.acmicpc.net/problem/2217문제N개의 로프 -> 물체를 들어올릴 수 있음각각의 로프의 길이와 굵기가 다름 -> 들 수 있는 물체의 중량이 서로 다를 수 있음But, 여러 개의 로프 병렬로 연결 -> 중량 나눌 수 있음ex. k개의 로프 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량 걸리게 됨=> 로프들에 대한 정보가 주어졌을 때, 들어올릴 수 있는 물체의 최대 중량?(모든 로프를 사용해야 할 필요 X, 임의로 몇 개의 로프를 골라서 사용해도 됨)입력첫째 줄: 정수 N (1 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량 (자연수, 출력: 들어올릴 수 있는 최대 중량풀이`int weight = arr[..
[BOJ/Greedy] 백준 1931 - 회의실 배정 (Java)
·
💻/코딩테스트
1931 - 회의실 배정https://www.acmicpc.net/problem/1931 문제한 개의 회의실 -> 사용하고자 하는 N개의 회의에 대하여 회의실 사용표각 회의 I에 대해 시작시간, 끝나는 시간각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 ㅐㄱ수(단, 회의는 한 번 시작하면 중간에 중단 X, 한 회의가 끝나는 것과 동시에 다음 회의 시작 O, 회의의 시작 시간과 끝나는 시간이 같을 수 있음 = 시작하자마자 끝나는 것)입력첫째 줄: 회의의 수 N (1 둘째 줄 ~ N + 1 줄: 각 회의의 정보 (회의 시작시간, 끝나는 시간)시작시간, 끝나는 시간 (자연수 or 0) 출력: 사용할 수 있는 회의의 최대 개수풀이끝나는 시간이 빠른 회의부터 선택끝나는 시간 기준으로 오름차순끝나는 시..
[BOJ/Greedy] 백준 11047 - 동전 0 (Java)
·
💻/코딩테스트
11047 - 동전 0https://www.acmicpc.net/problem/11047문제동전 총 N종류 -> 적절히 사용해서 가치의 합을 K로 만들려고 함=> 필요한 동전 개수의 최솟값?입력첫째 줄: N, K (1 둘째 줄부터 ~ N개의 줄: 동전의 가치 $A_i$ 오름차순 (1 = 2인 경우에 $A_i%는 $A_{i-1}$의 배수) 출력: K원을 만드는데 필요한 동전 개수의 최솟값풀이가장 큰 가치 동전부터 최대한 많이 사용int min = 0;for (int i = N - 1; i >= 0; i--) { if (A[i] 코드import java.io.*;import java.util.*;// 동전 0public class boj_11047 { public static void main(..
[BOJ/DP] 백준 1912 - 연속합 (Java)
·
💻/코딩테스트
1912 - 연속합https://www.acmicpc.net/problem/1912문제n개의 정수로 이뤄진 임의의 수열연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합ex. 10, -3, 3, 1, 5, 6, -35, 12, 21, -1-> 12 + 21 = 33 입력첫째 줄: 정수 n (1 둘째 줄: n개 정수로 이뤄진 수열(-1,000 출력: 가장 큰 합풀이`dp[i]`: i번째 수로 끝나는 연속합 중 최댓값`dp[i] = Math.max(arr[i], dp[i - 1] + arr[i])`i부터 새로 시작하기 or 이전 값에 i를 추가로 더하기(i까지의 연속합)코드import java.io.*;import java.util.*;// 연속합public class boj_1912 { ..
[BOJ/DP] 백준 11055 - 가장 큰 증가하는 부분 수열 / 11053 - 가장 긴 증가하는 부분 수열 (Java)
·
💻/코딩테스트
11055 - 가장 큰 증가하는 부분 수열https://www.acmicpc.net/problem/11055문제ex. 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우합이 가장 큰 증가하는 부분 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}=> 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것 ?입력첫째 줄: 수열 A의 크기 N (1 둘째 줄: 수열 A를 이루고 있는 $A_i$ (1 출력: 수열 A의 합이 가장 큰 증가하는 부분 수열의 합풀이`dp[i] = A[i]` => 자기 자신 포함`dp[i]`: i번째 원소를 마지막으로 하는 증가 부분 수열의 최대 합`dp[i] = Math.max(dp[i], dp[j] ..
kimmeoww
빙글빙글 돌아가는 Debug 하루