그리디10 [백준 17392] 우울한 방학 www.acmicpc.net/problem/17392 17392번: 우울한 방학 1일, 5일, 8일에 약속을 순서대로 배치하면, 4일과 10일에 각각 1만큼의 우울함을 느끼게 되어, 총 2만큼의 우울함을 느끼게 된다. 이보다 덜 우울함을 느끼게 만드는 방법은 존재하지 않는다. www.acmicpc.net 그리디 알고리즘 사용 식을 사용하는 문제이다. 우울함의 값은 기분이 음수일때 제곱을 해서 나타내므로 음수인 날이 적어야한다. 음수인 날을 커버할 수 있는게 약속의 기대행복값이다. 약속의 기대 행복값은 약속 당일 h 라면 하루가 지날수록 h-1 h-2..0까지 줄어든다. -> 그럼 약속 하나를 잡았을 때 기분이 0이상인 날은 h+1이란 의미다. 따라서 입력값을 받으면서 h+1을 sum에 더해준다. 이 su.. 2020. 12. 31. [백준 16112] 5차 전직 www.acmicpc.net/problem/16112 16112번: 5차 전직 메이플스토리 뉴비 키파가 드디어 레벨 200을 달성하고 5차 전직이라는 시스템을 이용해 캐릭터를 더욱 강력하게 만들려고 합니다. 5차 전직을 하려면 먼저 퀘스트를 통해 아케인스톤이라는 아 www.acmicpc.net 그리디 문제 예시 두 세가지 정도 확인하면 식을 세울 수 있다. 주의해야할 건 롱롱으로 인한 오버 플로우 처리.. 식 세우기 전체 n개의 퀘스트와 k개의 돌맹이를 활성화시킨다. A1 A2 A3 .... AN S1 S2 .. SK S1이 활성화된 이후 쌓이는 경험치는 A2 + A3 + ... + An S2에 쌓이는 경험치는 A3 + A4 + .. An Sk에 쌓이는 경험치는 Ak+1 .. + An 일 것이다. 정리하.. 2020. 12. 31. [백준 11501] 주식 www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 그리디 알고리즘을 사용한다. 문제 예시에서도 잠깐 비춰지지만 수열 전체가 오름차순이면 사서 파는게 이득이고 수열 전체가 내림차순이면 존버가 이득이다. 수열 전체가 내림차순인지 오름차순인지 앞에서 부터 순열을 돌아선 알 수 없다. 따라서 맨 뒤부터 숫자를 확인한다. 순열이 오름차순일수도 내림차순일수도 오르락 내리락 할수도 있다. 아마 대부분 오르락 내리락 할 것이다. 그렇다면 뒤에서 숫자를 확인하며 .. 2020. 12. 31. [백준 11399] ATM www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디를 사용하는 문제이다. 시간에 대해 오름차순 정렬 후 누적합을 계산해주면 된다. #include #include using namespace std; int n; int time[1000]; int main(void) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &time[i]); } sort(time, time + n); int bef = time[0]; int res .. 2020. 12. 29. 이전 1 2 3 다음
