[백준] 29704 - 벼락치기 (C++)

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

다양한 난이도의 문제 N개가 주어지고, 앞으로 T일의 제출 기한이 남아있다. 제출 기한 내에 문제를 제출하지 못하면 문제마다 정해진 벌금을 내야 한다. 혜민이는 하루에 한 문제만 해결할 수 있고, 가능한 적은 금액의 벌금을 내려고 한다. 문제를 해결하는 데 소요되는 일수와 그 문제를 제출 기한 내에 해결하지 못할 경우 내야 하는 벌금이 주어질 때, 혜민이가 내야 하는 벌금의 최소 금액을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N, T, d_i  ≤ 1,000
• 1 ≤ m_i ≤ 5,000

 

i번째 과제를 풀거나 풀지 않았을 때 내지 않아도 되는 벌금의 최댓값을 저장할 dp[2][N+1] 배열을 선언해야 한다.

• 남은 일수가 과제 해결 소요 시간보다 많거나 같다면, 문제를 해결할 수 있다. 이때, 해결하거나 해결하지 않는다는 두 가지 선택을 할 수 있다.
• 남은 일수가 과제 해결 소요 시간보다 적다면, 문제를 해결할 수 없으므로 i-1번 문제까지 해결한 경우의 금액과 동일하다.

 

i번째 dp 배열이 i-1번째 dp 배열에만 영향을 받기 때문에 bool 값을 이용해 메모리를 절약할 수 있다. 또, 남은 일수가 과제 해결 소요 시간보다 작을 때만 갱신되기 때문에, 아래 정답 코드처럼 dp 배열을 2차원 대신 1차원으로 구현해 메모리를 절약할 수 있다.

[백준] 12865 - 평범한 배낭 (C++)

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, T 입력받기
2. N개의 문제 해결 소요 시간과 벌금을 입력받으면서 dp 배열 갱신하기
   1. 모든 벌금의 총합 저장
   2. 남은 일수가 과제 해결 소요 시간보다
      1. 많거나 같은 경우, 이전 dp 배열을 참고해서 i번째 과제를 해결하거나 해결하지 않았을 때 벌금이 최소화되는 걸 선택해 dp 배열 값 갱신하기
      2. 적은 경우, 이전 dp 배열 값으로 갱신하기
3. 모든 벌금의 총합에서 dp[tog][t] 값을 빼서 내야 할 벌금의 최솟값 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
using namespace std;

int n,t,dp[2][1001],d,m,sum;
bool tog;

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

    cin >> n >> t;
    for (int i=1; i<=n; i++) {
        cin >> d >> m;
        sum += m;
        tog = (i%2==0 ? 0 : 1);
        for (int j=1; j<=t; j++)
            if (j-d>=0) dp[tog][j] = max(dp[!tog][j-d]+m,dp[!tog][j]);
            else dp[tog][j] = dp[!tog][j];
    }
    cout << sum - dp[tog][t];
}