Algorithm/Greedy (43) 썸네일형 리스트형 (C++) - 백준(BOJ) 1931번 : 회의실배정 답 www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정렬 후 회의가 끝나는 시간이 가장 낮은 회의 순으로 배정하시면 됩니다. 풀이방법 1. 회의가 끝나는 시간을 기준으로 오름차순 정렬 2. 회의가 끝나는 시간이 같을경우엔 회의 시작시간을 기준으로 오름차순 정렬 3. 끝시간이 다음 회의 시작 시간보다 작을 때는 회의를 배정 4. 배정했던 회의개수 답 출력 Code #include #include #include using namespace std; int n; int ans; vector v(100000); bool cmp(const pair &a, const pair &b){ i.. (C++) - 백준(BOJ)코딩 11047번 : 동전0 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net greedy 문제였습니다. greedy로 푸는 것이 수학적으로 맞는지를 검증하는지가 중요합니다. 감으로 의존해 푸시면 제대로 문제를 풀 수 없습니다. 좋은 방법 중 하나는 귀류법으로 자신이 세운 가정이 맞는지를 증명해보는 것입니다. 귀류법을 통해 현재 최대 이익을 얻지 않으면 발생되는 손해가 있는지의 여부를 알 수 있습니다. 풀이방법 귀류법으로 증.. (C++) - 백준(BOJ)코딩 1026번 : 보물 www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net greedy 문제였습니다. 풀이방법 상식적? 감으로 생각했을 때 S의 값을 가장 적게 만들기 위해서는 제일 작은 수를 제일 큰 수끼리 짝지어서 곱해주었을 때 그 합이 최소가 됩니다. 문제에서 B의 수는 재배열하면 안되지만 A는 옮길 수 있습니다. 이 말은 자칫 B를 고정하고 A를 한 칸씩 옮기는 brute force를 생각할 수 있으나 A,B 둘다 옮길 때와 A의 원소들만을 옆으로 옮겨줄 때는 같다는 생.. 이전 1 ··· 3 4 5 6 다음