본문 바로가기

greedy5

[백준문제풀이] 1931 회의실배정 풀이일시 : 2020-10-16 문제 : 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 : 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진.. 2021. 1. 1.

[백준문제풀이] 2217 로프 풀이일시 : 2020-09-02 문제 : N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력: 첫째 줄에 정수 N이 주어.. 2020. 12. 30.

[백준문제풀이] 11399 ATM 풀이일시 : 2020-09-02 문제 : 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에,.. 2020. 12. 30.

[백준문제풀이] 11047 동전0 풀이일시 : 2020-09-02 문제 : 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) ex) 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 출력: 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. ex) 6 풀이 :.. 2020. 12. 30.

[기본문제풀이] greedy 알고리즘 풀이 일시 : 2020-08-29 그리디알고리즘 : 당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다. 대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다. 문제 : 총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라 풀이 : 가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다. #include using namespace std; //총 몇개의 동전을 거슬러 줘야되는가 int main() { int n, result = 0; cin >> n; result += n / 500; n %= 500; //나머지 연산을 해서 다음 레이어로 간다. result += n / 100; n %= 100; result += n / 50; .. 2020. 12. 29.

이전 1 다음

티스토리툴바