algorithm/Greedy (7) 썸네일형 리스트형 [C++] BOJ 15889 호 안에 수류탄이야!! 문제 백준 15889번 호 안에 수류탄이야!! https://www.acmicpc.net/problem/15889 15889번: 호 안에 수류탄이야!! 게임이 조용히 마무리 될 수 있으면 “권병장님, 중대장님이 찾으십니다”를, 그렇지 않으면 “엄마 나 전역 늦어질 것 같아”을 출력한다. www.acmicpc.net 코드 #include #include using namespace std; int pos[30003], dist[30003]; bool visited[30003]; int main() { int n; cin >> n; for (int i = 0; i > pos[i]; if (n == 1) { cout > dist[i]; int next = dist[i] + pos[i.. [C++] BOJ 1715 카드 정렬하기 문제 백준 1715번 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 코드 #include #include #include using namespace std; int n, ans = 0; int main() { priority_queue pq; cin >> n; for (int i = 0; i > num; pq.push(num); } while (pq.size()>1).. [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 코드 #include using namespace std; int n, k, cnt = 0; int val[11]; int main() { cin >> n >> k; for (int i = 0; i > val[i]; while (k > 0) { for (int i = n - 1; i >= 0; i--) { if (k >= .. [C++] BOJ 12782 비트 우정지수 www.acmicpc.net/problem/12782 12782번: 비트 우정지수 진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같 www.acmicpc.net 코드 #include #include using namespace std; int t; char num1[1000005], num2[1000005]; int main() { cin >> t; while (t--) { cin >> num1 >> num2; int change_one = 0, change_zero = 0; for (int i = 0; num1[i] != '\0'; i++) { if (num1[i].. [C++] BOJ 11256 사탕 www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 코드 #include #include using namespace std; int t, j, n; int box[1005]; int main() { cin >> t; while (t--) { cin >> j >> n; int a, b; int cnt = 0; for (int i = 0; i > a >> b; box[i] = a * b; } sort(box, box + n); for (i.. Greedy (탐욕) 알고리즘 그리디 알고리즘이란? 매 순간 최선의 방법(탐욕적인) 방법을 선택하는 알고리즘. 전체적으로 봤을 때도 최적의 선택인지 알 수 없으므로 특정 조건 하에 써야 한다. 계산속도가 빠르다는 장점이 있다. 어떤 상황에서 쓸 수 있을까? 1. 탐욕 선택 속성: 탐욕적으로 선택하더라도 문제의 최적해가 보장될 때 2. 최적 부분 구조: 부분 문제의 최적해가 전체 문제의 최적해로 확장될 수 있을 때 [C++] BOJ 1439 뒤집기 www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 코드 #include #include using namespace std; int main() { string str; int num0 = 0, num1 = 0; cin >> str; str[0] == '0' ? num0++ : num1++; for (int i = 1; i < str.size(); i++) { if (str[i] != str[i - 1]) { str[i] == '0' ? num0++ : num.. 이전 1 다음