전체 글
BOJ 1931 회의실 배정
boj 1931 회의실 배정 그리디 알고리즘 문제의 풀이 흐름에 따라 풀었다. 현재 시간을 t라고 할 때, t이상의 회의들 중에 가장 먼저 끝나는 회의를 선택하는 것이 최선이라고 생각했다. 증명까지는 하지 못했고, 그림을 그려보고 당장 손해이지만 나중에는 이득인 경우가 있나 확인해보았다. 입력 받은 회의의 시간들을 끝나는 시간이 빠른 순으로, 끝나는 시간이 같을 때는 시작하는 시간이 빠른 순으로 정렬한 후에 가장 먼저 끝나는 회의를 찾는 방식으로 구현했다. #include #include #include using namespace std; int N; int ans = 0; int t = 0; pair p[100005]; bool compare(const pair& p1, const pair& p2) ..
BOJ 11047 동전 0
boj 11047 동전 0 그리디 알고리즘을 활용하여 풀 수 있는 문제여서 적용하여 풀어보았다. DP를 활용한 풀이도 생각할 수 있는 문제이지만, DP를 활용할 경우 O(NK)의 시간복잡도로 시간초과가 나와 그리디를 활용해야만 하는 문제였다. 그리디 알고리즘 문제의 풀이 흐름에 따라 풀어보았다. 직관적으로 높은 금액의 동전을 최대한 많이 사용할 수록 동전 갯수가 적어질 거라고 생각했다. 위 생각을 증명해보았다. 간단하게 하기 위해 동전의 가치가 10, 50, 100, 500원 뿐이라고 한다. '동전을 최소로 소모하여 값을 지불하기 위해서는 500원은 최대한, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보자. 증명을 편히 하기 위해 먼저 '..