[BOJ 백준] 1757번 : 달려달려 (C++)

[BOJ 백준] 1757번 : 달려달려 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. N분간 달리고 각 시간 별로 지침 지수가 존재하므로 [x분 달리기][y 지침 지수]에 대한 데이터 저장 배열 필요

2. 현재 [x분][y 지침 지수]에 도달할 수 있는 방법은 두 가지

  1) 달린다. ▶ 지침 지수 1 증가 [x-1분][y-1 지침 지수]에서 [x분][y 지침 지수]에 도달

  2) 쉰다. ▶ 지침 지수가 1분마다 1씩 감소해서 0으로 도달 ▶ [x-1][1], [x-2][2]... [x-m][m]에서 [x][0]에 도달

  3) 연속으로 쉰다. ▶ [x-1][0], [x-2][0],...[x-n][0]에서 [x][0]에 도달 ▶ [x-1][0]이 [x-2][0]의 데이터를 포함 ▶ [x-1][0]만 처리

3. N분일 때, 지침 지수는 0이므로 [N][0]을 출력

과정

먼저, N분의 시간 동안 달리거나 쉰다는 옵션을 선택할 수 있습니다.

그래서, 각 시간마다 지침 지수 한계치인 m까지 도달할 수 있어 2차원 배열인 [x분 달리기][y 지침 지수]를 필요로 합니다.

 

여기서, 1분부터 선택할 수 있으므로, 0분인 데이터 공간이 필요합니다.

또한, 지침 지수도 0부터 m까지 존재할 수 있어, [N+1][M+1]의 크기를 가진 배열이 필요합니다.

 

매 시간마다, 달리거나 쉰다는 선택지를 가질 수 있습니다.

달리기를 선택하는 경우, 해당 시간에 이동하는 거리만큼을 더해줘야 합니다.

반면에, 쉬기를 선택하는 경우, 달리는 거리를 더할 수 없습니다.

가장 먼 거리를 달린 경우를 찾는 것이므로, 달리거나 쉰다는 선택 중 어떤 선택을 하더라도 반드시 최대 거리 값을 저장해야 합니다.

이를 예제 입력 문제를 통해서 시뮬레이션을 해보겠습니다.

 

먼저, 각 시간별로 달린 경우, 이동하는 거리 데이터와 경과 시간별 지침 지수 배열입니다.

 

이를 바탕으로, 1분부터 시뮬레이션을 돌려보겠습니다.

 

1-1) 1분에서 달린다면, 0분에서 지침 지수를 1 더하고, 1분에서 달릴 수 있는 거리를 추가로 더해줘야 합니다.

단, 0분에서 지침 지수는 1이 될 수 없으므로, 1분에서의 지침 지수 2는 무시합니다.

 

1-2) 1분에서 쉰 경우입니다. [1][0]로 오는 데이터는 [n-1][1], [n-2][2], ... [n-x][x]입니다.

또한, 연속으로 쉬는 경우도 있으므로 [n-1][0]에서도 도달할 수 있습니다.

이 중에서, 가장 큰 값을 찾아야 합니다.

하지만, 0분의 경우 지침 지수는 존재할 수 없으므로 항상 [1][0]도 0으로 기록됩니다.

 

2-1) 2분에서 달린 경우입니다.

이전 시간에서 지침 지수가 1 증가해야 합니다.

따라서, [2][2]는 [1][1]에서 도달할 수 있고, [2][1]은 [1][0]에서 도달 가능합니다.

 

 

2-2) 2분에서 쉰 경우입니다.

이전 시간의 지침 지수를 모두 소모하거나 연속으로 쉴 수 있습니다.

그래서, 연속으로 쉰 [1][0]에서와 지침 지수를 모두 소모하는 [1][1], [0][2]에서 도달 가능합니다.

[0][2]는 존재할 수 없으나, 초기에 0으로 초기화했으므로 무시하고 계산해도 됩니다.

 

[1][0], [1][1], [0][2] 중 가장 멀리 이동한 경우는 [1][1]입니다.

그래서, [2][0]에는 [1][1]의 데이터를 대입합니다.

 

3-1) 3분에서 달린 경우입니다.

이전 시간에서 지침 지수가 1 증가해야 합니다.

따라서, [3][2]는 [2][1]에서 도달할 수 있고, [3][1]은 [2][0]에서 도달 가능합니다.

 

3-2) 3분에서 쉰 경우입니다.

이전 시간의 지침 지수를 모두 소모하거나 연속으로 쉴 수 있습니다.

그래서, 연속으로 쉰 [2][0]에서와 지침 지수를 모두 소모하는 [2][1], [1][2]에서 도달 가능합니다.

 

[2][0], [2][1], [1][2] 중 가장 멀리 이동한 경우는 [2][0]입니다.

그래서, [3][0]에는 [2][0]의 데이터를 대입합니다.

 

위 과정을 5분까지 반복하겠습니다.

4-1) 4분에서 달린 경우

 

4-2) 4분에서 쉰 경우

 

5-1) 5분에서 달린 경우

 

5-2) 5분에서 쉰 경우

 

 

마지막 시간에서 지침 지수는 항상 0이여야 합니다.

따라서, [5][0]의 값인 9를 출력하면 됩니다.

 

주의점

1. 초기에 [달린 시간 : 1분][지침 지수 : 2]처럼, 존재할 수 없는 경우에 대해 처리하지 않으면, 오답을 출력할 수 있습니다.

 

2. 문제에서 별다른 조건이 없었으므로, 연속으로 쉬는 경우도 존재합니다.

[n-1][0]은 [n-2][0]부터 [0][0]까지 연속으로 쉬거나 중간중간마다 연속으로 쉰 경우를 모두 포함하므로, [n-1][0]만 처리하면 됩니다.

---

03. 정답 코드

// 골드 4 - 1757번 : 달려달려
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

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

    // 운동할 시간 N, 지침 한계 지수 M
    int N, M;
    cin >> N >> M;

    vector<int> dists(N+1);
    vector<vector<int>> results(N+1, vector<int>(M+1, 0));

    // 현재 지침 지수와 시간에 따라 도달할 수 있는 경우
    // 1. 쉰다. -> [n-1][m+1]에서 도달
    // 2. 달렸다. -> [n-1][m-1]에서 도달

    for(int n = 1; n < N+1; n++)
    {
        cin >> dists[n];

        for(int m = 0; m < M+1; m++)
        {
            // 1. 쉰다.
            // [n-1][1], [n-2][2], [n-3][3]... 에서 도달
            // [n-1][0] ~ [1][0] 에서 도달
            if(m == 0) 
            {
                // [n-1][1], [n-2][2], [n-3][3]... 에서 도달
                for(int rest_time = 1; rest_time < M+1; rest_time++)
                {
                    int prev_n = n - rest_time;
                    // 그 이전에는 뛴 경우가 없어서
                    if(prev_n > 0 == false) break;  
                    results[n][0] = max(results[n][m], results[prev_n][rest_time]);
                }
                // [n-1][0] ~ [1][0] 에서 도달
                // 어차피 [n-1][0]에서 [n-2][0]~[1][0] 중 최댓값을 포함
                results[n][0] = max(results[n][0], results[n-1][0]);

            }
            // 2. 달렸다. -> [n-1][m-1]에서 도달
            // 단, 현재 지침 지수가 0이거나 시간과 지침 지수가 이론 상 존재하지 않을 때, 제외
            if(m != 0 && n - m >= 0) results[n][m] = max(results[n][m], results[n-1][m-1] + dists[n]);
        }
    }

    cout << results[N][0] << "\n";
}

 

---

04. 마무리

연속으로 쉬거나 도달할 수 없는 경우에 대한 처리를 미리 생각하지 못했다면, 해결하는데 시간이 더 걸렸을 것 같았습니다.

 

 

---

 

읽어주셔서 감사합니다.

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