백준: 17979, 17976, 17977

</br> 2019 본선 중 골드 문제 풀기
</br>

17979: What’s Mine is Mine

https://www.acmicpc.net/problem/17979

대충 (시작 시간), (종료 시간), (번호)가 주어지면,
{(종료 시간) - (시작 시간)} * 미네랄[번호] 만큼 벌 수 있다
스케줄링 문제

#include <bits/stdc++.h>

using namespace std;

int mi[101];
tuple<int, int, int> task[10001];
int dp[15001];
int m, n;

bool cmp(const tuple<int, int, int> &t1, const tuple<int, int, int> &t2){
    if( get<0>(t1) == get<0>(t2) ){
        if( get<1>(t1) == get<1>(t2) ){
            return get<2>(t1) > get<2>(t2);
        }
        return get<1>(t1) < get<1>(t2);
    }
    return get<0>(t1) < get<0>(t2);
}

int func(int now){
    if( dp[now] ) return dp[now];
    if( now == n ) return get<2>(task[now]);

    int ma = 0;
    for(int i = now + 1; i <= n; i++){
        if( get<0>(task[i]) >= get<1>(task[now]) )
            ma = max(ma, func(i));
    }
    ma += get<2>(task[now]);

    dp[now] = max(func(now+1), ma);
    return dp[now];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m >> n;

    for(int i = 0; i < m; i++){
        cin >> mi[i];
    }
    for(int i = 1; i <= n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        task[i] = make_tuple(a, b, (b-a)*mi[c-1]);
    }

    sort(task+1, task+n+1, cmp);

    cout << func(1) << endl;

}

재귀 + dp
일단 입력 받을 때 (시작, 종료, 가중치)로 미리 계산 해서 저장했다.
그 후 시작 시간이 빠르고, 종료 시간이 빠르고, 가중치가 큰 순으로 정렬한다.
dp[i] = max(i를 넣는 경우, i를 안 넣는 경우)로 식을 세웠다.
i를 넣는 경우, i와 겹치지 않는 애들을 다 구해서 최댓값을 찾으면 된다.
i를 넣지 않는 경우, 그냥 func(i+1)로 구할 수 있다.

</br>

17976: Thread Knots

https://www.acmicpc.net/problem/17976 점이 존재할 수 있는 선분이 여러 개 주어지는데, 각 선분 위에 점을 하나씩 골라서 각 점들 사이의 거리의 최소가 가장 크게 하기

#include <bits/stdc++.h>

using namespace std;

pair<int, int> lines[100001];
int n;

bool func(int d){
    int a = lines[0].first;
    for(int i = 1; i < n; i++){
        if( lines[i].first - a >= d ) a = lines[i].first;
        else if( lines[i].second >= a + d ) a = a + d;
        else return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        lines[i] = make_pair(a, a+b);
    }

    sort(lines, lines+n);

    long long ans = 0;
    long long l = 0, r = INT_MAX;
    while( l < r ){
        long long mid = (l+r) / 2;
        if( func(mid) ){
            l = mid;
            if( ans == mid ) break;
            ans = max(ans, mid);
        }
        else{
            r = mid;
        }
    }

    cout << ans << endl;

}

일단 입력 받을 때 (시작점, 종료점)으로 바꿔서 저장했고, 작은 순으로 정렬한다
그 다음, 가능한 길이를 이분탐색하면 된다

현재 탐색 중인 길이: d
이전 선분의 점: a
현재 선분: (s, e)   라고 하면

만약 s-a >= d 라면 현재 선분의 시작점과 이전 점이 충분히 먼 것이므로 현재 선분의 점은 s로 고정
만약 e >= a+d 라면 현재 선분의 안에 이전 점과 d만큼 띄워진 점을 찍을 수 있으므로 현재 선분의 점은 a+d로 고정
둘 다 아니면 점을 못 찍는다. 따라서 return false

</br>

17977: Triangulation

https://www.acmicpc.net/problem/17977

#include <bits/stdc++.h>

using namespace std;

int dp[1000001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    dp[3] = 0;
    dp[4] = 1;
    for(int i = 5; i <= n; i++){
        dp[i] = dp[(i+1)/2] + 2;
    }

    cout << dp[n] << endl;

}

점화식 찾기 너무 어렵다…
dp 아니면 안 풀리겠지 싶어서 이전 도형에 삼각형을 덧붙인다고 생각했다
예시에 육각형을 보니 안에 삼각형이 있는 데서 알았다

육각형: 삼각형 + 주변에 삼각형 3개
팔각형: 사각형 + 주변에 삼각형 4개
십각형: 오각형 + 주변에 삼각형 5개

즉 짝수각형은 내부의 (짝수/2)각형의 모든 변에 다른 삼각형들을 붙은 것과 같으므로, 걔네들의 거리가 더해지니 +2 해야 한다

</br>

---

수학 문제 빼고는 풀이 법은 바로 떠오르는데 수학 문제가 참
</br>