[C++]백준 27446번 랩실에서 잘 자요

📌문제 링크

---

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

📌문제 설명

---

dp[i] = i번째 문서까지의 최소 비용 그리디하게 푸는건 풀이를하며 떠오르지 않아서 dp를 이용하여 문제를 풀이했습니다.

📌코드

---

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

vector<int> dad;
bool doc[101];
int N, M, dp[101]; // dp[i] = i번째 문서까지의 최소 비용

// 입력을 받는 함수
void input(){
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int d; cin >> d;
        doc[d] = true; // 문서가 있음
    }
}

// 문제를 해결하는 함수
void solve(){
    input(); // 입력 받기
    for(int i = 1; i <= N; i++){
        int cnt = 1;
        if(doc[i]){
            dp[i] = dp[i - 1]; // 문서가 있는 경우
        }
        else{
            dp[i] = dp[i - 1] + 7; // 문서가 없는 경우
        }
        for(int j = i - 1; j >= 1; j--){
            cnt++;
            dp[i] = min(dp[i], dp[j - 1] + 5 + 2 * cnt); // 최소 비용 계산
        }
    }
    cout << dp[N]; // 결과 출력
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve(); // 문제 해결 함수 호출
    return 0;
}