본문 바로가기

탐욕알고리즘9

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 요약 N 개의 종류의 동전이 있고 각 동전은 무수히 많다. 동전을 조합해서 가치의 합을 K로 만들려고 할 때 필요한 동전의 최소 개수를 구하는 문제이다. 풀이 첫 번째 예제 입력값을 보자 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000의 가치를 가진 동전들로 4200원을 만들어야 .. 2022. 3. 10.
BOJ 15748 Rest Stops 문제 링크 : https://www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net 요약 으.. 영어 문제 간단하게 해석해보자면 Farmer John과 Bessie가 등산을 한다, Jhon과 .. 2022. 3. 10.
BOJ 1700 멀티탭 스케줄링 문제 링크 : https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 요약 멀티탭의 구멍 개수와 전기용품의 사용 횟수 K가 주어지고 K개만큼의 전자용품을 사용한 순서대로 전자용품 이름(숫자)이 주어지는데 가장 플러그를 덜 빼고 모든 전기용품을 사용할 수 있는 방법을 구하는 문제이다. 풀이 어떻게 풀어야 할지는 빠르게 떠올랐다. 하지만 구현이 생각보다 까다로웠던 문제.. 빈 멀티탭이 있다면 비어있는 공간에 우선적으로 끼워준다. 현재 사용해야 하는 전기용.. 2022. 3. 10.
BOJ 13904 과제 문제 링크 : https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 요약 정수 N과 N개의 과제 마감일까지 d(남은 일수)와 w(과제점수)를 입력받는다. 과제는 하루에 한 개만 할 수 있을 때 받을 수 있는 가장 많은 점수를 출력하는 문제이다. 풀이 일다 점수를 최대한 많이 받으려면 기간내에 가장 많은 과제를 수행해야 하고 기간이 겹친다면 큰 점수를 선택하여야 한다. pair로 d와 w를 입력받고 남은 기간 순으로 일단 정렬을 해준다. 정렬한 순서대로 일수를 카운트해주면서 점수를 더해주다가 일.. 2022. 3. 10.

티스토리툴바