Twinparadox Factory

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄부터 N개 줄에는 각 토핑의 열량 Di가 한 줄에 하나씩 주어진다. (1 ≤ Di ≤ 10000) 출력첫째 줄에 최고의 피자의 1달러 당 열량을 출력한다. 소수점 이하는 버리고 정수 값으로 출력한다. 소스코드 #include #include #include using namespace std; int main(void) { int n, a, b, c, d[100], sum, toping, bil; double max = 0;..

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다. 출력강호가 받을 수 있는 팁의 최대값을 출력한다. 소스코드 #include #include #include #include using namespace std; int main(void) { int n, tmp; long long sum = 0; vector arr; cin >> n; for (int i = 0; i > tmp; arr.push_back(tmp); } sort(arr.begin(), arr.end..

Algorithm] Knapsack(배낭 문제) - 동적계획법 처음 내가 알고리즘 문제를 접했을 때 처음으로 배낭 문제를 접근했던 방식은 그리디였다.그리디는 다들 알고 있듯, 선택에 대한 번복도 없고, 근시안적인 선택으로 인해서경우에 따라서는 최적해를 보장하지 못하는 문제가 발생한다. 모든 배낭 문제에 대해서 그리디가 유효한 방법이 될 수 없는 건 아니고,물건을 임의로 쪼개어 담을 수 있는(용량을 정할 수 있는) 배낭 문제라면,무게 당 가격을 계산해서 적당히 담는 걸 고려하여 최적해를 구할 수 있기 때문에그리디 알고리즘으로는 해결이 가능하며 이를 부분 배낭(Fractional Knapsack)문제라고 한다.그러나, 일반적인 배낭 문제에서는 물건을 쪼개서 담을 수 없어서 다른 방식을 고려해야 한다. 이 때..

Algorithm] 작업 스케줄링(Task Scheduling) 기계에서 수행하는 n개의 작업(T1, T2, T3, ... , Tn)이 있고,각 작업에 시작 시간과 종료 시간이 존재한다고 할 때 최소한의 기계를 배치하면서모든 작업을 수행하도록 하는 문제를 작업 스케줄링이라고 한다.이 때 수행 시간이 중복되지 않게 모든 작업을가장 적은 수의 기계에 배정하는 최적해를 구하는 문제라는 것에 초점을 두자. 작업 스케줄링 문제에서 우리가 다룰 수 있는 변수와알 수 있는 정보에 대해서 조금 생각해보도록 하자. 작업의 수 n과, 각 작업들의 시작 시간과 종료 시간이 기본적으로 입력값으로 들어올 것이다.이건 입력값을 통해서 우리가 알 수 있는 정보고문제를 살펴봤을 때 우리가 알 수 있는 정보가 하나 더 있다.그 어떠한..

2011년 한국정보올림피아드(KOI) 초등부 문제 : 저울 이 문제의 답안과 채점은 Jungol이라는 사이트에서 이뤄졌다.(문제 번호 2499 : 저울) 필자는 두 가지 답안을 작성했다.그리디 알고리즘을 통해 최적해를 구하는 방법을 잘못 접근했기 때문인데,최대에서 최소로 최적해를 구성하면서 TLE(시간 초과) 문제가 발생해서 만점을 받지 못했고,최소에서 최대로 최적해를 구성하는 건, TLE 문제를 해결할 수 있었다. 아주 간단한 원리를 까먹고 진행해서... 1안 : TLE 발생 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include using namespace std;int ma..

Greedy Algorithm(그리디 알고리즘;탐욕 알고리즘) 데이터 간 관계를 고려 않고 수행 과정에서 모든 것들을 욕심 내어최솟값 혹은 최댓값을 가진 데이터를 선택한다.이러한 선택을 근시안적인 선택이라고도 하며이러한 선택으로 그리디 알고리즘은 문제의 최적해를 찾는다. 그리디 알고리즘에서 선택이 이뤄지면 번복하지 않고 다른 것을 취하지 않기 때문에알고리즘 자체는 매우 단순하지만, 제한적인 경우에만 이 알고리즘이 유효하게 사용할 수 있다. 대표적인 예가 동전 거슬러주기(Coin Change)문제이니 이를 토대로 알고리즘에 대해서 알아보자. 현실처럼 500원, 100원, 50원, 10원이 있다고 하자.거스름돈 동전의 수가 가장 적은 최적해를 구하고 싶을 때, 그리디 알고리즘으로 해결할 수 있다.그리디 알고..