개인공부용123 프로그래밍 블로그

문제 : https://algospot.com/judge/problem/read/LUNCHBOX 첫번째 줄에는 테스트 케이스의 수 두번째 줄에는 도시락의 수가 주어지고 세번째 줄에는 도시락 별 도시락을 데우는데 걸리는 시간 네번째 줄에는 도시락 별 도시락을 먹는데 걸리는 시간이 주어진다. 이 문제에서 도시락 데우는 데 걸리는 시간은 무조건 일정합니다.(도시락을 먹기전에 데워야하기 떄문에) 그러므로 이 문제에서는 먹는 시간을 최소화하는것이 중요합니다. 이 문제의 경우 탐욕법을 이용하면 쉽게 풀수있습니다. 탐욕법을 사용하기위해서 먹는순서가 가장 오래걸리는거 부터 먹게 sorting했습니다. #include #include #include using namespace std; typedef struct { i..

문제 : https://algospot.com/judge/problem/read/MATCHORDER 한국 팀과 러시아팀의 레이팅이 주어지고 한국팀이 이길수있는 최대 승수를 출력하는 문제입니다. 이 문제는 dp를 이용해서 풀수있지만 그럴경우 시간복잡도가 커지게됩니다. 그러므로 탐욕법을 이용해서 풀었습니다.이길수있는 경기는 가장 레이팅이 비슷한 선수를 이용해서 이기고 무조건 지는경기라면 가장낮은 레이팅의 선수를 내보내서 최적해를 구합니다. #include #include #include using namespace std; vector Rus; vector Kor; int N; int order() { int wins = 0; multiset Ordered_Kor(Kor.begin(),Kor.end()); ..

문제 : https://algospot.com/judge/problem/read/SUSHI 주어진 예산에서 최대의 선호도를 찾는 문제입니다. 이때 주어질수 있는 예산의 최대값은 2,147,483,647입니다. 이 수를 이용해서 배열을 만드는게 불가능하므로슬라이딩 윈도 기법을 이용해서 배열의 수를 줄여야합니다. budget 부분의 최대 선호도를 구하기위해서는 budget - 20000 미만의 숫자는 필요가 없습니다.그리고 물건의 값은 100의 배수이므로 예산과 물건값을 100으로 나눠줍니다. #include #include #include using namespace std; int menu[20][2]; //0 은가격 1은 선호도 int cache[201]; // 다음 예산의 값을 정할떄 budget -..