그리디 알고리즘

3. 당장 좋은 것만 선택하는 그리디

• 어떠한 문제가 있을 때 단순 무식하게 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 탐욕적으로 접근했을때 정확한 답을 찾을 수 있다는 보장, 정당한지 검토해야 한다.
• 어떤 코딩 테스트 문제를 만났을 때, 바로 유형 파악이 어렵다면 그리디를 의심하자
• 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는 가?
  1. 다양한 아이디어를 고려해보자.
  2. 풀이 방법을 하나씩 고민해보자.

3.1 동전 고르기

n = 1260
count = 0
list = [500,100,50,10]
for coin in list:
	count += n // coin
    n%=coin
    
print(count)

3.2 큰 수의 법칙

시간 제한 : 1초
메모리 제한 : 128MB
배열이 주어지고, M번 더하는데 K번 연속해서 더해질 수 없다.
배열의 크기 N (2 ≤ N ≤ 1000), 숫자가 더해지는 횟수 M (1 ≤ M ≤ 10,000), K (1 ≤ K ≤ 10,000)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int answer=0;
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> v(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin>>v[i];
    }
    sort(v.begin(),v.end(),greater<int>());
    for(int i=0; i<M/(K+1); i++){
        answer+=v[0]*K;
        answer+=v[1];
    }
    if(M%(K+1)!=0)answer +=v[0]*(M%(K+1));
    cout<<answer;
}

3.3 카드 고르기

NxM개의 카드가 주어질 때, 행을 고른다.
이 행을 골랐을 때 이 행들중 가장 작은 수를 뽑는다.
어떤 행을 뽑아야 가장 큰 수를 뽑을 수 있는 가?
($1 \leq N,M \leq 100$), ($E \leq 10,000, \space E \in \mathbb{V}$)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> least_from_row;
    for(int i=0; i<N; i++){
        int least = INT_MAX;
        for(int j=0; j<M; j++){
            int temp;
            cin>>temp;
            if(least>temp){
                least = temp;
            }
        }
        least_from_row.push_back(least);
    }
    cout<<*max_element(least_from_row.begin(),least_from_row.end());
}

3.4 1이 될때 까지

N($2 \leq N \leq 10,000$) 과 K($2 \leq K \leq N$)이 주어질 때, 두가지 연산을 해서 1로 만드는 최소 횟수를 구하여라.
1. N에서 1을 뺀다
2. N이 K로 나누어 떨어지면, N을 K로 나눈다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int answer = 0;
    int N, K;
    cin >> N >> K;
    // for small N,K
    /* while (N != 1)
    {
        if (N % K == 0)
            N /= K; //
        else
            N--;
        answer++;
    } */
    // for larger N,K
    while (N != 1)
    {
        if(N<K)break;
        if (N % K == 0)
        {
            N /= K; 
            answer++;
        }
        else{
            int target = (N/K)*K; //fast substitution   
            answer+=N-target;
            N-=N-target;
        }
    }
    cout << answer+(N-1);
}