그리디, Dp

현재 순간에서 좋아보이는 것을 선택하는 것은 그리디이다. 즉, 이전의 값에 상관 없이 무조건 현재 상태에서 최선을 선택한다.

dp는 이전 값을 사용하여 현재 값을 구하는 것, 현재값은 미래에 사용

백트래킹은 모든 경우를 다 해보는 것

 

그리디로 동전 최소 사용횟수 구하는 문제에 적용하려면

동전들이 서로 배수와 약수의 관계여야함

ex) 70, 50, 10의 경우에는 불가능하다.

#include <iostream>
using namespace std;

int main()
{
    int coin, cnt = 0 ;
    cin >> coin;
    int num[4] = {500, 100, 50, 10};
    for(int i=0; i<4; i++)
    {
        if(coin / num[i] == 0)
            continue;
        int temp = coin / num[i];
        cnt += temp;
        coin = coin % num[i];
    }
    cout << cnt;
    return 0;
}

 

 

회의실 배정

각 시간별로 최대 선택 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[9], cnt[9];
int main()
{
    int maxNum = 0;
    fill(arr, arr+9, -1);
    fill(cnt, cnt+9, -1);
    for(int i=0; i<7; i++)
    {
        int s, e;
        cin >> s >> e;
        if(arr[e] < s)
            arr[e] = s;
    }
    
    for(int i=0; i<9; i++)
    {
        cnt[i] = maxNum;
        if(arr[i] == -1)
            continue;
        int temp = cnt[arr[i]] + 1;
        if(temp > maxNum)
        {
            cnt[i] = maxNum = temp;
        }
    }
    cout << maxNum;
    return 0;
    
}

전체 시간동안 제일 회의실 많이 선택

#include <iostream>
#include <vector>
using namespace std;
struct Node
{
    int s, e;
};
vector<Node> t;

bool compare(Node a, Node b)
{
    if(a.e == b.e)
        return a.s < b.s;
    
    return a.e < b.e;
}
int main()
{
    for(int i=0; i<7; i++)
    {
        int s, e;
        cin >> s >> e;
        t.push_back({s, e});
    }
    sort(t.begin(), t.end(), compare);
    int cnt = 0, end = 1;
    for(int i=0; i<7; i++)
    {
        if(t[i].s <= end)
        {
            cnt++;
            end = t[i].s;
        }
    }
    cout << cnt;
    return 0;
}

 

dp는 많이 풀어서 유형을 익히는 것이 좋음

짧은 시간안에 해답을 생각해내는 것이 쉽지 않음.

최단경로와 최소 비용

#include <iostream>
using namespace std;
int map[4][4] = {
    0, 10, 5, 10,
    1, 30, 20, 1,
    1, 10, 3, 1,
    2, 90, 5, 0
}, cal[4][4];
int main()
{
    for(int i=1; i<4; i++)
    {
        cal[i][0] = cal[i-1][0] + map[i][0];
        cal[0][i] = cal[0][i-1] + map[0][i];
    }
    for(int i=1; i<4; i++)
    {
        for(int j=1; j<4; j++)
        {
            int temp = cal[i-1][j];
            if(temp > cal[i][j-1])
                temp = cal[i][j-1];
            cal[i][j] += temp + map[i][j];
        }
    }
    cout << cal[3][3];
    return 0;
}

 

enum을 통해 가독성 좋게 하기