백준46 [백준 2217] 로프 - 자바 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net 1. 풀이 각 로프마다 들 수 있는 중량이 있으며, k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/.. 2020. 4. 3. [백준 5585] 거스름돈 - 자바 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 1. 풀이 그리디 알고리즘을 사용하면 쉽게 풀 수 있는 문제입니다. 동전의 큰 숫자부터 나누어가며 나눠지면 나눠지는 만큼 누적하면 됩니다.. 2020. 4. 3. [백준 1931] 회의실배정 - 자바 https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 풀이 종만북에도 나오는 그리디 알고리즘의 개념을 이해하는데 도움을 주는 문제입니다. 문제의 목표는 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾기 입니다. 조건은 아래와 같습니다. 1. 회의가 한번 시작하면 중간에 중단 될 수 없습니다. 2. 한 회의가 끝나는 동시에 다음 회의가 시작될 수 있습니다. 3. 회의의 시작 시간과 종료시간이 같을 수도 있습니다. ( 시작하자마자 끝났다고 간주 ) 이 문제를 시각화하면 아래와 같습니다. 회의가 일찍 끝나는 기준으로 그리디를 전개하면 사.. 2020. 4. 3. [백준 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 1. 풀이 아주 쉬운 그리디 문제입니다. 문제에 오름차순으로 입력이 들어온다고 했으므로, 큰 돈부터 차례대로 나누어 가면서 나누어지면 더하고, 나머지 값들을 대상으로 계속해서 나누어가면 됩니다. 2. 코드 import java.util.*; public class Main { public static void main(String[].. 2020. 4. 3. [백준 11399] ATM - 자바 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 풀이 제일 기본적인 그리디 알고리즘 문제 중 하나입니다. 그리디 알고리즘이란 매 순간마다 최적의 선택을 하여 정해진 목표까지 계산해 나가는 것을 의미합니다. DP랑 비슷해보이지만, DP는 모든 경우를 저장하여 계산하는 것이고, 그리디는 순간순간 최적의 경우만 저장하여 최적의 수로만 진행하는 것을 의미합니다. 이 문제의 경우 줄에 선 사람들의 순서대로 인출하는데 걸리는 시간을 최소화 하는 것이 목표이다. 그러므로 걸리는 시.. 2020. 4. 3. [백준 12865] 평범한 배낭 - 자바 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 1. 풀이 DP관련 알고리즘 수업때 항상 나오는 문제인걸로 알고 있습니다. knapsack 알고리즘이라고도 하죠. 처음엔 완전탐색(브루트-포스)로 해볼려고 했으나, O(2^n)의 시간복잡도를 가지므로 포기했습니다. 그리디 알고리즘도 가격이나, 무게중 하나를 탐욕적으로 계산을해도 최.. 2020. 4. 2. 이전 1 ··· 3 4 5 6 7 8 다음
