그리디

14 Mar 2022

Reading time ~1 minute

그리디 알고리즘;탐욕법

현재 상황에서 지금 가장 좋은 것만 고르는 방법
=> 현재의 선택이 나중에 미칠 영향을 고려하지 않는다.

그리디 알고리즘으로 풀이할 때는 반드시 정당성을 검토해야한다.

큰 수의 법칙

배열로 주어진 수들을 M번 더하여 가장 큰 수로 만드는 법칙

제한 사항

같은 수를 연속해서 K번 초과 더할 수 없다.
다른 인덱스여도 같은 수는 같은 수로 취급한다.

풀이

가장 큰 수와 다음으로 큰 수를 찾아 조건에 맞게 더한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    vector<int>v;
    int N,M,K,temp,result,count;
    cin>>N>>M>>K;
    for(int i=0;i<N;i++){
        cin>>temp;
        v.push_back(temp);
    }
    sort(v.rbegin(),v.rend());
    count=M/(K+1)*K+M%(K+1);
    result=v[0]*count+v[1]*(M-count);
    cout<<result<<"\n";
    return 0;
}

숫자 카드 게임

최솟값 중 최댓값 찾기

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main(){
    int n,m,input_n;
    cin>>n>>m;
    priority_queue<int,vector<int>>min;
    for(int i=0;i<n;i++){
        priority_queue<int,vector<int>,greater<int>>temp;
        for(int j=0;j<m;j++){
            cin>>input_n;
            temp.push(input_n);
        }
        min.push(temp.top());
    }
    cout<<min.top()<<"\n";
}

1이 될 때까지

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,k,result=0;
    cin>>n>>k;
    while(n>=k){
        if(n%k!=0){
            result+=(n%k);
            n-=(n%k);
            
        }
        n/=k;
        result++;
    }
    cout<<result<<endl;
    return 0;
}