#include #include using namespace std;int main(){ vector stair; vector dp; int count; cin >> count; stair = vector(count, 0); dp = vector(count, 0); for (int i = 0; i > stair[i]; } dp[0] = stair[0]; dp[1] = stair[0] + stair[1]; dp[2] = max(stair[0] + stair[2], stair[1] + stair[2]); for (int i = 3; i  풀이1. 계단의 정보를 저장하고 직접 최대값이 나올 수 있는 방법을 찾아본다.2. 직접 찾는 방법으로 dp를 만든다.dp0 = arr0dp1 = arr0 + arr1dp2 ..

#include #include #include using namespace std; bool sortCompare(vector a, vector b) { return a[1] = end) { answer++; end = targets[i][1]; } } return answer; } 풀이 1. 끝지점이 작은순으로 정렬해준다. 2. 끝지점과 다음 시작점이 맞닿았다면 해당 끝지점으로 바꿔준..

#include #include #include using namespace std; //변환 횟수, 제거한 0개의 개수 //길이로 이진변환 vector solution(string s) { vector answer(2, 0); while(s.length() > 1) { int count = 0; answer[0]++; for(int i = 0; i 0) { s += count % 2 == 1 ? "1" : "0"; count /= 2; } } return answer; } 풀이 1. 0을 지워가며 지워진 0의 개수 저장 ..

#include #include using namespace std; bool FindAnswer(int n, int k, const vector &stones) { int count = 0; for(int i = 0; i < stones.size(); i++) { if(stones[i] - n = k) { return true; } } return false; } int solution(vector stones, int k) { int start = 0; int end = 0; int mid; //find end for(int i = 0; i < stones.size(); i++) { end = max(end, stones[i]); } while(start

#include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; sort(A.begin(), A.end()); sort(B.begin(), B.end()); int index = 0; for(int i = 0; i < B.size(); i++) { if(A[index] < B[i]) { index++; answer++; } } return answer; } 풀이 1. 낮은 순으로 정렬해준다. 2. A를 B로 하나씩 비교하면서 최대한 작은 수로 이길 수 있게 유도한다. 느낀점 탐욕적 풀이들은 웬만하면 다 쉽게 생각해야 쉽게 풀리는 것같다. 더 쉽게 생각해보자. https://school.prog..

#include #include using namespace std; vector solution(int n, int s) { int num = s / n; //나눌 수 없다면 if(num == 0) { return vector(1, -1); } vector answer(n, num); int extraPlus = s % n; //추가분을 더해준다. n=4, s=14일 경우 끝에서 부터 1씩더해주어 3344이다. while(extraPlus > 0) { answer[answer.size() - extraPlus]++; extraPlus--; } return answer; } 풀이 1. 평균 값을 최대한 곱해주는 것이 최고의 곱이 된다. 2. s / n가 자연수의 최소 값이고 나머지가 있다면 1씩 나눠서 ..