문제 링크: https://www.acmicpc.net/problem/17521 17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net 그리디 알고리즘 다음 날에 가격이 증가하면 코인을 모두 매수하고, 감소하면 코인을 모두 매도하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include using namespace std; typ..

문제 링크: https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 그리디 알고리즘 연속된 숫자를 한 번에 뒤집을 수 있기 때문에, 먼저 연속된 숫자들을 하나로 합쳐줍니다. 그리고 남은 숫자들 중에서 개수가 더 적은 숫자를 하나씩 뒤집어주면 됩니다. 0001100 -> 010 -> 000 (1번) 1234567891011121314151617181920#include#include#includeusing namespace std; int main() ..

문제 링크: 그리디 알고리즘 연속된 색은 한 번에 칠할 수 있기 때문에, 이를 하나의 색으로 만들어줍니다. 그다음 가장 많은 개수의 색으로 전체를 먼저 칠한 후 나머지 색으로 하나씩 칠하면 됩니다. BBRBRBBR -> BRBRBR -> BBBBBB -> BRBBBB -> BRBRBB -> BRBRBR 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); int n; cin >> n; string s; cin >> s; char prev = s[0]; for (i..

문제 링크: https://www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 그리디 알고리즘 매 순간 두 음료를 선택하여, 양이 더 적은 음료를 버린다면 에너지 드링크의 양을 최대로 만들 수 있습니다. 따라서, 우선 음료를 오름차순으로 정렬한 뒤에 가장 양이 많은 음료에 나머지 음료를 순차적으로 버리면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include ..

문제 링크: https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 그리디 알고리즘 "XXXX"를 찾아서 모두 AAAA로 바꿔주고 그다음 "XX"를 찾아서 모두 "BB"로 바꿔주면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include using namespace std; string s; int main() { ios_base::sync_with_stdio(false); cin >> s; while (s.find("XXXX") != string::npos) { s.repl..

문제 링크: https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 다이나믹 프로그래밍(DP), 수학 파스칼 삼각형을 아래 그림과 같이 왼쪽으로 정렬된 형태로 생각하면 2차원 배열로 쉽게 표현할 수 있습니다. 그러면 맨 왼쪽을 모두 1로 채운 뒤 ㄱ자 모양으로 파스칼 삼각형 DP 배열을 채우면 됩니다. 123456789101112131415161718192021222324252627282930313233343536#include#include#includeusing na..

문제 링크: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net BFS 알고리즘 큐에 다음 두 가지를 삽입하는 BFS를 구현하면 되는 문제입니다. 1. cur * 2 2. cur * 10 + 1 큐가 비워지기 전에 A == B가 되는 수를 찾으면 성공이고 큐가 비워졌을 때 A == B가 되는 수를 못 찾으면 실패입니다. 숫자 맨 뒤에 1을 추가하는 것은 2로 나누어 떨어지지 않기 때문에 숫자에 2를 곱한 것과 중복되지 않습니다. 따라서 방문 체크 배열을 만들 필요가 없습니다. 숫자는 최대 10^9이므로 2번 연산에서 10^9 * 10 + 1을 하면 int의 최대 크기를 넘..

문제 링크: https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 그리디 알고리즘 최대한 비싼 가격을 무료로 지불해야 하므로 내림차순으로 정렬해서 인덱스를 3으로 나누었을 때 나머지가 2인 가격을 무시하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include #include using namespace std; int n; int c[100000..