PS/그리디 알고리즘[Greedy] 25

백준 1449 수리공 항승

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net #include #include #include using namespace std; int main() { int n,l; int cnt=1; cin>>n>>l; int *list = new int[n]; for(int i=0;i>list[i]; } sort(list,list+n); int start = list[0]; for(int i=1;il) //좌우 0.5 간격이기 때문에..

백준 18310 안테나

https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net #include #include #include #include #include using namespace std; bool com(pair a, pair b) { if(a.second==b.second){ return a.first < b.first; } return a.second < b.second; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);..

백준 2812 크게 만들기

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include #include #include using namespace std; bool check; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin>>n>>k; vectorv; //기존 입력 값 숫자 vectorv2;//변경된 결과 값 숫자 string num; cin>>num; for(int i=0;i

백준 2012 등수매기기

https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net #include #include #include #include using namespace std; int main() { int n; cin>>n; vectorv; unsigned long long sum=0; for(int i=0;i>a; v.push_back(a); } sort(v.begin(),v.end()); for(int i=0;i

백준 9009 피보나치

https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net #include #include #include using namespace std; int main() { int t; int dp[46]; dp[0]=0; dp[1]=1; for(int i=2;i>t; for(int i=0;i>n; for(int j=45; j>=1; j--){ if(dp[j]