그리디 알고리즘2 [그리디 #4] BOJ 1744 - 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1차 시도 큰 수끼리 곱하면 된다고 막연하게 생각했다. 근데 예제를 보면 예외가 몇 개 포함되어 있다. 1. 1일 때는 곱하면 안된다. 2. 0일 때는 음수랑만 곱한다. 그런데 반례를 찾을 수 있었다. 5 -3 -2 -1 1 2 답: 8 출처: 맨 아래 블로그 큰 음수끼리 곱해야 가장 커진다는 점을 간과했다. 접근방법 그래서 전체적인 프로세스를 구상했다. 준비 1. 양수, 0, 음수를 각각의 v.. 2024. 2. 7. [그리디 #3] 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 접근 방법 예제를 보면 쉽게 해결할 수 있는 문제이다. 최종적으로 모든 카드의 합이 최소가 되어야 한다. 최소가 되기 위해선 당연하게 가장 작은 카드 2개를 선택하면 된다. 매우 간단하게 해결할 수 있는 그리디 문제이다. #include #include #include using namespace std; vector v; int n, m; int main().. 2024. 2. 5. 이전 1 다음
