코드 포스 (Code Forces) - Alice And Books (C++)

 

 

N개의 책과 각 책이 보유한 페이지 수가 주어진다.

각 책은 입력된 순서대로 1~N의 번호가 부여되어 있다.

 

이 때, N개의 책을 두 그룹으로 나눌 것이다. (각 그룹에는 최소한 1개의 책이 존재한다.)

Alice는 각 그룹에서 가장 번호가 높은 책을 하나씩 읽을 것이다.

 

가능한 경우 중에서, Alice가 읽을 수 있는 페이지 수의 총합의 최대값은 얼마인가?

 

문제 풀이

특정 알고리즘을 사용하기 보단, 아이디어를 떠올려 푸는 문제이다.

 

먼저, 모든 책을 두 그룹으로 나눈다면, 두 그룹 중 하나에는 반드시 N번째의 책이 포함되어 있을 것이다.

해당 그룹에선, 무슨 일이 있어도 N번째의 책을 읽을 수 밖에 없다. (N보다 큰 번호를 부여받은 책은 없으므로)

 

즉, 어떠한 경우에든 N번째의 책은 반드시 읽힌다. 그렇다면, N번째 책을 제외한 나머지 하나의 책의 페이지 수가 최대일 때의 앨리스가 읽은 페이지 수의 총합이 최대값이 될 것이다. 

 

즉 N번째 책을 제외한, 나머지 책 중 페이지수가 가장 많은 책이 해당 그룹에서 가장 높은 번호를 가지도록 그룹을 나누면 된다. (만약, M번째의 책이 N번째 책을 제외한 책중 페이지 수가 가장 많다면, 1~M, M+1~N으로 두 그룹을 나누어 M번째책과 N번째 책을 읽도록 할 수 있다.)

 

아이디어만 떠올리면 아주 간단하게 코드로 작성할 수 있다.

 

풀이 코드

테스트 케이스의 개수에 대한 입력은 제외하고, 코드를 설명할 것이다.

int NumBook = 0;
std::cin >> NumBook;

std::vector<int> Pages(NumBook);
for (int i = 0; i < NumBook; i++)
{
	std::cin >> Pages[i];
}

먼저, 입력을 받아 저장해주자.

책의 수와 각 책의 페이지 수를 저장해 주었다.

int Answer = Pages[NumBook - 1];

이후, N번째 책의 페이지 수를 Answer에 더해주자. (N번째의 책은 어떠한 경우에든 반드시 읽으므로)

int MaxPage = 0;
for (int i = 0; i < NumBook - 1; i++)
{
    MaxPage = std::max(MaxPage, Pages[i]);
}

N번째 책을 제외한 나머지 책들 중 페이지 수가 가장 많은 책을 탐색해주자.

Answer += MaxPage;

위에서구한 값을 Answer에 더해주면 끝이다.

Answer을 출력해주면 된다.

  

코드 전문

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

int main()
{
    int NumTestCase = 0;
    std::cin >> NumTestCase;

    std::vector<int> Answers(NumTestCase);

    for (int Case = 0; Case < NumTestCase; Case++)
    {
        int NumBook = 0;
        std::cin >> NumBook;

        std::vector<int> Pages(NumBook);
        for (int i = 0; i < NumBook; i++)
        {
            std::cin >> Pages[i];
        }

        int Answer = Pages[NumBook - 1];

        int MaxPage = 0;
        for (int i = 0; i < NumBook - 1; i++)
        {
            MaxPage = std::max(MaxPage, Pages[i]);
        }

        Answer += MaxPage;
        Answers[Case] = Answer;
    }

    for (int i = 0; i < NumTestCase; i++)
    {
        std::cout << Answers[i] << std::endl;
    }

    return 0;
}