https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net 그리디 알고리즘을 사용한다. 문제 지문을 관찰해보면 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실 이라는 언급이 있다. 이를 통해서 유추해 볼 수 있는 사실으로, 어떠한 수 K에서 피보나치 수 F를 빼서 k를 만들면, 그 새로운 수 k도 다시 피보나치 수들의 합으로 나타낼 수 있다는 것을 알 수 있다. 어떠한 수를 피보나치 수 F들의 합으로 구성한다고 할 ..

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 부분합 + 그리디 문제. 꿀벌 둘을 A,B ( B가 더 오른쪽에 있는 꿀벌 ) 벌통을 C로 두면 크게 세가지 경우의 수가 있을 수 있다. 1. A < B < C 순 배치. 이 경우에 있어서, 꿀통인 C는 오른쪽 끝에 위치하는것이 가장 이득이 되고, 첫번째 꿀벌 A는 가장 왼쪽 끝에 위치하는것이 가장 이득이 된다. 남은 꿀벌 B가 어디에 있느냐에 따라서, (전체 꿀 + B~C 이동에서의 꿀 - A, B지점에서의 꿀) 을 계산해주면 된다. 벌이 있는 곳에서는 꿀을 딸 수 없기 때문에 A, B 지점의 꿀은 계산에서 따로 빼줘야 함에 유의할것...

https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 굉장히 빠르게 풀어내서 만족스러운 문제. 일단 쉽게 관찰할 수 있는 첫번째 특징으로, 입력으로 들어온 $h_k$ 들의 합 $sum$ 이 반드시 3의 배수여야만 한다. 두 물뿌리개를 동시에 사용하면 물이 3만큼 뿌려지게 되기 때문이다. 예제 입력 4로 설명해주고 있는 또다른 조건의 하나로, 이 조건으로 인해 골드5라는 티어를 배정받지 않았나 싶다. 나무 하나를 2만큼 성장시키는 물뿌리개는 아무리 뿌려도 짝수 높이만큼의 나무를 만들 수 있기 때..

https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 그리디 문제. 스네이크버드보다 높이가 작은 과일들을 먹는데에는 아무런 제한이 없기 때문에, 높이가 작은 과일들을 먼저 먹지 않을 이유가 없다. 입력으로 들어온 $h_i$를 정렬해서 작은순으로 먹게 하면 된다. #include using namespace std; vector v; int main(){ int N,M,k; cin >> N >> M;..

https://www.acmicpc.net/problem/13413 13413번: 오셀로 재배치 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검 www.acmicpc.net 두가지 작업 중에 첫번째 작업을 하는것이 당연히 훨씬 이득이기 때문에, 첫번째 작업을 최대한 많이 진행할 수 있게 만들어주면 되는 그리디 문제에 해당한다. 일단 문자열 A와 B의 i번째 문자 $A_i$, $B_i$ 에 대해서, 각각 W,B 에 해당하는경우 N와 B,W에 해당하는 경우 M를 세준다. W,B와 B,W 쌍이 만들어지는 경우, 첫번째 작업을 진행할 수 있으므로 두번의 두번째 작업을 사용할 ..

https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 실제 등수가 1,2,3,4,5.... 차가 1로 일정한 증가하는 수열의 형태를 띄고 있고, 문제 입력으로 들어온 수열을 해당 수열과 최대한 비슷한 형태로 구성하는 문제이다. 최대한 비슷한 형태 >> 정렬된 배열을 지칭하는 말로, 입력으로 들어온 배열을 정렬해서 인덱스값+1 과 비교해서 불만도의 총 합을 구하면 된다. 입력으로 들어온 배열을 구성할 때 $i N_j$ 인 상황에서 불만도의 합인 $Total$..