알고리즘!/Greedy3 [C/C++] 백준 1931: 회의실 배정 (풀이) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 Greedy 알고리즘 중에서 제일 유명한 문제라고 할 수 있다. 한개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의 중에 회의실을 사용할 수 있는 회의의 최대 개수를 구하면 된다. 결론부터 말하자면 끝나는 시간이 제일 빠른 회의부터 차례대로 진행할 때 회의의 개수가 최대가 된다. 각 경우마다 가장 이득이 되는 선택을 하면 되는데 그 각각의 선택이 전체적으로도 가장 이득이 되는 대표적인 예이다. 구현은 끝나는 시간 순서대로 오름차순으로 정렬을 한다. 이때 한가지 주의해야할 점은 회의의 시작시간과 끝.. 2023. 9. 5. [C] 1026: 보물 결국 함수 S를 최소화하기 위해 배열 A를 재배열 해야한다. 최소화 하기 위해서는 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해줘야지만 S의 값이 최소가 된다. 이 문제에서는 B에 있는 수를 재배열하면 안된다고 했지만 어차피 문제는 답만 맞으면 된다는 생각으로 A는 오름차순으로 B는 내림차순으로 정렬한뒤 같은 index끼리 곱해주었다. 사실 이 문제와 완전 같은 방식으로 하기 위해서는 이차원 배열 두 개를 만든 뒤 현재 남아있는 A배열에 가장 작은 수와 B배열에 남아있는 가장 큰 수를 곱해주고 그 수는 지나갔다는 표시를 남겨주어 다음번에 이 수는 아예 빼고 생각하도록 코드를 짜면 된다. #include int arrA[51]; int arrB[51]; void swap(in.. 2023. 8. 25. [C/C++] 1541: 잃어버린 괄호 이 문제는 -가 언제 나오냐가 중요하다. -가 나올 때 그 다음 -가 나올때 까지 합을 빼는 것이 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 것이다. 또한 -가 나올 때마다 다음 -가 나올 때까지 합을 빼는 것이 가장 최소이기 때문에 현재에 이익이 문제 전체의 이익이 되는 Greedy 알고리즘의 일종이다. 나는 배열 2개만 써서 구현하였지만 아예 -가 나올 때마다 부분 집합을 만들어서 (slice를 통해) 각 값을 더하거나 빼서 구현할 수도 있을 것 같다!! 아래는 소스코드다!! #include #include char arr[52]; int store[3]; int ContinueCalculate(int i,int max) { if(arr[i]=='+') { store[0]+=store[1]; s.. 2023. 8. 24. 이전 1 다음
