백준 10740번 ACM

문제 링크입니다: https://www.acmicpc.net/problem/10740

알고리즘 대회에서 각각의 단계에 속한 문제들 중 제일 쉬운 문제를 푸는 전략을 고수할 때 최소 점수를 출력하라는 문제였습니다.

위와 같은 조건만 주어졌을 경우 엄청 쉬운 문제이지만, 모든 열을 적어도 한번 이상은 사용해야한다고 명시되어있기 때문에 DP를 이용하여 풀어야하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 각각의 문제 난이도를 입력 받을 때 부분합도 같이 계산해줍니다.

2. 첫 번째 단계 문제에서 0 번째 열, 1 번째 열, 2 번째 열에서 시작하는 경우로 나뉘기 때문에 세 가지 경우를 모두 고려해줘야합니다.

3. 아래와 같이 두 가지의 경우를 고려해줘야합니다.

i) 해당 단계에서 푼 문제의 열과 이전 단계에서 푼 문제의 열과 같은 경우

a) 모든 열을 한번씩은 사용해야하기 때문에 다음 문제도 같은 열을 사용할 수 있는 경우는 인덱스 (N-3)까지입니다.

b) 다음 문제를 해당 열과 다른 열을 이용하여 풉니다.

ii) 해당 단계에서 푼 문제의 열과 이전 단계에서 푼 문제의 열이 다른 경우

a) 모든 열을 한번씩은 사용해야하기 때문에 다음 문제도 해당 단계와 같은 열을 사용할 수 있는 경우는 인덱스 (N-2)까지입니다.( i)의 a)와 달리 두개의 열은 사용했다는 것이 보장되었기 때문에)

b) 다음 문제들을 이전과 현재 단계와 다른 열들로만 풉니다.(부분합 이용하여 바로 계산)

4. 3번이 진행될 떄마다 해당 열에서 정한 문제의 난이도를 결과에 더해줍니다.

4. 3번과 4번을 반복한 결과 제일 최소를 출력해줍니다.

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 150000 + 1;

const int INF = 987654321;

 

int N;

int arr[3][MAX];

int pSum[3][MAX];

int cache[3][3][MAX]; //현재, 이전, 인덱스

 

int minSum(int cur, int prev, int idx)

{

        int &result = cache[cur][prev][idx];

        if (result != -1)

                 return result;

 

        result = INF;

        //현재 열과 이전 열이 같을 경우

        if (cur == prev)

        {

                 //모든 열을 최소 한번 사용해야하므로 인덱스 (N-3)까지는 동일 열 사용 가능

                 if (idx < N - 3)

                         result = minSum(cur, prev, idx + 1);

                 //다른 열 사용

                 for (int i = 0; i < 3; i++)

                         if (i != cur)

                                 result = min(result, minSum(i, cur, idx + 1));

        }

        //다를 경우

        else

        {

                 //한번은 다른 열 사용했으므로 인덱스 (N-2)까지는 동일 열 사용 가능

                 if (idx < N - 2)

                         result = minSum(cur, prev, idx + 1);

                 //여기서 또 다른 열을 쭉 사용(부분합 이용)

                 for (int i = 0; i < 3; i++)

                         if (i != cur && i != prev)

                                 result = min(result, pSum[i][N] - pSum[i][idx + 1]);

        }

       

        //해당 난이도를 더해준다

        result += arr[cur][idx];

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < 3; i++)

                 for (int j = 0; j < N; j++)

                 {

                         cin >> arr[i][j];

                         pSum[i][j + 1] = pSum[i][j] + arr[i][j];

                 }

 

        memset(cache, -1, sizeof(cache));

        int result = INF;

        //0, 1, 2에서 각각 시작해봐야한다

        for (int i = 0; i < 3; i++)

                 result = min(result, minSum(i, i, 0));

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~