목록알고리즘/Greedy (7)

키베이루's diary

[C++] 백준 1049번 기타줄

1) 문제설명 2) 아이디어 상점에서 파는 기타 줄의 패키지와 낱개의 개수가 제한이 없으므로 패키지 또는 낱개의 가격이 가장 저렴한 것만 구입을 한다고 생각하면 쉽게 풀린다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int n, m; int result, temp; int arr[10001], brr[10001]; int main() { cin >> n >> m; for (int i = 0; i > arr[i] >> brr[i]; } sort(arr, arr + m, less()); sort(brr, brr + m, less()); // 패..
알고리즘/Greedy 2022. 10. 17. 13:22
[C++] 백준 2217번 로프

1) 문제설명 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2) 아이디어 문제에 대해서 잘 이해하기만 하면 쉽게 풀 수 있는 과제이다. 로프가 견딜 수 있는 무게가 10, 20 인 경우 각각 10, 10을 들면 되므로 최대 중량은 20이 된다. 다른 예로 로프가 견딜 수 있는 무게가 10, 20, 30 인 경우 10의 무게로 3개의 로프가 전부 다 견딘 다면 최대 중량은 30이 된다. 하지만 전부다 사용할 필요 없이 20, 30의 ..
알고리즘/Greedy 2022. 6. 8. 08:51
[C++] 백준 1449번 수리공 항승

1) 문제설명 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 2) 아이디어 입력받은 배열을 오름차순으로 정렬하고 앞에서 뒤를 뺀 결과만큼 테이프를 소모한다. 그리고 테이프를 모두 소모하면(테이프의 길이가 1보다 작을 경우) 테이프를 다시 리셋시켜준다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; ..
알고리즘/Greedy 2022. 5. 31. 23:29
[C++] 백준 2847번 게임을 만든 동준이

1) 문제설명 https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 2) 해결방법 반복문을 2개 이용하여 입력받은 배열이 오름차순이 될 때까지 뒤에서부터 1씩 빼주고 그 과정을 진행할 때마다 카운트를 +1씩 늘려준다. 이후 카운트를 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long dp[1000..
알고리즘/Greedy 2022. 5. 31. 05:09
[C++] 백준 15903번 카드 합체 놀이

1) 문제설명 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 2) 해결방법 처음 입력값 두 개를 더해서 저장한 후 그 값을 다시 입력값에 저장한다. 이후 반복문을 돌면서 오름차순으로 계속 정렬을 한 후 다시 과정을 반복한다. 3) 코드 #include #include #include #include #include #include using namespace std; long long arr[500002]..
알고리즘/Greedy 2022. 5. 22. 06:47
[C++] 백준 2012번 등수 매기기

1) 문제설명 2) 해결방법 입력값을 오름차순으로 정렬한 뒤 그 값과 그 값의 인덱스 값을 빼주어 더해주었다. 3) 코드 #include #include #include #include #include #include using namespace std; long long arr[500002]; /* 등수 매기기 해결방안 입력값을 오름차순으로 정렬한 뒤 그 값과 그 값의 인덱스 값을 빼주어 더해주었다. */ int main() { long long n; cin >> n; for (int i = 1; i > arr[i]; } sort(arr+1, arr + n+1); long long sum = 0; for (long long i = 1; i i) { sum = sum + arr[i] - i; } else..
알고리즘/Greedy 2022. 5. 22. 03:33
[C++] 백준 11497번 통나무 건너뛰기

1) 문제설명 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 2) 해결방법 입력값 중 가장 큰 값을 중앙에 두고 양옆으로 작아지게 수를 정렬한 후 앞뒤 값의 차이들 중 최댓값을 출력하면 된다. 13 10 12 11 10 11 12 -> 10 11 12 13 12 11 10으로 정렬 한 뒤 | 10 vs 11 | 11 vs 12 |... | 11 vs 10 | 앞뒤 차이들 중 최댓값을 출력한다. 입력값을 오름차순으로 정렬한 뒤 짝수 인덱스를 ..
알고리즘/Greedy 2022. 5. 20. 23:44
Prev 1 Next