[BOJ 백준] 1988번 : 낮잠 시간(C++)

[BOJ 백준] 1988번 : 낮 (C++)

00. 시작 전

 

정글 게임랩 과정도 거의 끝나가서 다시 백준 재활 운동을 시작하려고 합니다..

백준 문제 풀이는 가끔씩 글을 써보도록 하겠습니다.

 

01. 개요

출처

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

 

문제

입력

출력

예시

 

---

02. 접근 방식

아이디어 및 상태 정의

처음에는 단순히 '현재까지 몇 개의 구간을 사용했는지'만 알면 된다고 생각했습니다.

하지만 문제를 다시 분석해 보니 직전 구간(m-1)의 사용 여부가 현재 구간 선택에 직접적인 영향을 미친다는 것을 알게 되었습니다.

따라서, 다음과 같은 3차원 DP 배열을 설계했습니다.

• DP 상태: dp[직전 구간 사용 여부][사용 중인 구간 개수][현재 검사 중인 구간 인덱스]
  • dp[0][ j ][ i ] : i번째 구간을 사용하지 않고, 총 j개의 구간을 선택했을 때의 최댓값
  • dp[1][ j ][ i ] : i번째 구간을 사용하고, 총 j개의 구간을 선택했을 때의 최댓값

 

복잡도 분석

문제의 제한 조건은 N=3'000, B=3'000 (최악의 경우), 메모리 제한 128MB, 시간 제한 2초입니다.

 

공간 복잡도

• 데이터 타입 : 각 구간의 최댓값이 200'000이므로 3'000(구간 개수) * 200,000 = 600'000'000(6억)입니다. 이는 int 범위 내에 충분히 수용 가능합니다.
• 메모리 계산 : 4Byte(int) * 2 * 3'000 * 3'000 = 72'000'000Byt = 72MB
• 결론 : 메모리 제한인 128MB 내에 안정적으로 들어옵니다.

(p.s. 메모리 줄이라고 하면, 현재 몇 번째 구간을 검사하는지에 대한 부분을 크게 압축시킬 수도 있을 것 같습니다.)

 

 

시간 복잡도

• 연산 횟수 : 구간 개수 N * 선택 개수 B = 3'000 * 3'000 = 9'000'000
• 결론 : 1억 번 연산을 대략 1초로 잡을 때, 900만 번의 연산은 2초 내에 충분히 해결 가능합니다.

 

점화식 설계

n번째 구간을 검사할 때 발생할 수 있는 경우는 두 가지입니다.

 

Case 1: 현재 구간을 사용하는 경우

다음 두 가지 상황 중 최댓값을 선택합니다.

1. 직전 구간을 사용한 경우: dp[1][ j-1 ][ n-1 ] + 현재 구간 값
2. 직전 구간을 사용하지 않은 경우: dp[0][ j-1 ][ n-1 ] (현재 구간을 처음으로 시작하는 경우)

 

Case 2: 현재 구간을 사용하지 않는 경우

직전 구간의 사용 여부와 상관없이 이전까지의 최댓값을 유지합니다.

1. 직전 구간을 사용했던 경우: dp[1][ j ][ n-1 ]
2. 직전 구간을 사용하지 않았던 경우: dp[0][ j ][ n-1 ]

---

03. 정답 코드

// 골드 4 - 1988번 : 낮잠 시간
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 2s / 128 MB
// 3 <= N <= 3000
// 2 <= B <= N
// 0 <= val <= 200'000

// B 개수
// 반복문 1~N
// M번째 -> [연속 여부][개수][M-1] = 최댓값으로부터 검사

// 현재 M번째
// 사용 O -> [1][개수-1][M-1]에서 더해서 가져오기 / [0][개수-1][M-1]에서 그냥 가져오기
// 사용 X -> [1][개수][M-1]에서 바로 가져오기 / [0][개수][M-1]에서 바로 가져오기

// 2 * 3000 * 3000 * 4 = 72MB
// 3000 * 3000 = 9'000'000 * 4?
// 200'000 * 3'000 = 600'000'000

vector<int> g_vals;
vector<vector<vector<int>>> g_temps;

void inputData(int N)
{
    g_vals = vector<int>(N);

    for(int& val : g_vals)
        cin >> val;
}

void calculate(int N, int B)
{
    g_temps = vector<vector<vector<int>>>(2, vector<vector<int>>(N, vector<int>(N, 0)));

    // i번째
    for(int i = 1; i < N; i++)
    {
        // 사용한 구간 개수별로 검사
        for(int j = 1; j < B; j++)
        {
            // 사용 O
            g_temps[1][j][i] = max(g_temps[0][j-1][i-1], g_temps[1][j-1][i-1] + g_vals[i]);

            // 사용 X
            g_temps[0][j][i] = max(g_temps[0][j][i-1], g_temps[1][j][i-1]);
        }
    }
}

int getResult(int N, int B)
{
    int result = 0;
    for(int i = 0; i < B; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            result = max(result, g_temps[j][i][N-1]);
        }
    }
    return result;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 개수 N, 구간 B
    int N, B;
    cin >> N >> B;

    inputData(N);
    calculate(N, B);
    cout << getResult(N, B) << "\n";

    return 0;
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!