17127번 벚꽃이 정보섬에 피어난 이유

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

예제 1

7

2 5 3 1 4 2 3

2 + 5 + 3 + (1 * 4 * 2 * 3)

             index=  0 1  2  3 4  5  6

vector<int> vc = {2, 5, 3, 1, 4, 2, 3};

'+'로 활용하려 할 때만, true가 되고, index를 활용한다.

use[0] = true;

use[1] = true;

use[2] = true;

가 되어버리고,(덧셈이므로 add 변수에 저장)

나머지는 곱셈이다.(mul 변수에 저장)

주의할 점은

곱셈은 '연속'으로 나와야한다.

덧셈은 무조건 3개가 되어야 하고

곱셈은 전체(=N) - 3개가 되어야 한다.

곱셈의 개수(used[i]가 false인 것의 개수)가 N - 3개가 아니면 return 해버린다.

정답 코드 2개를 올린다.

하나는 내가 직접 푼 코드이고, 다른 코드는 다른 분의 좋은 아이디어를 참고하였다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, ans = 0;
 
vector<int> v;
 
bool used[11] = { false, };
 
void simulation(int pos, int cnt)
{
    if (cnt == 3)
    {
        int c = 0;
 
        for (int i = 0; i < v.size() - 1; i++)
        {
            if(!used[i])
            {
                while (!used[i] && i < N)
                {
                    ++i;
                    ++c;
                }
 
                if (c != N - 3) return;        
            }
        }
 
        int add = 0, mul = 1;
 
        for (int i = 0; i < v.size(); i++)
        {
            if (used[i]) add += v.at(i);            
            else mul *= v.at(i);        
        }
 
        int sum = add + mul;
 
        ans = max(ans, sum);
 
        return;
    }
 
    for (int i = pos; i < v.size(); i++)    
        if (!used[i])
        {
            used[i] = true;
 
            simulation(i + 1, cnt + 1);
 
            used[i] = false;
        }    
}
 
int main(void)
{
    int n = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &n);
 
        v.push_back(n);
    }
 
    simulation(0, 0);
 
    printf("%d\n", ans);
 
    return 0;
}

아래 코드에서 k가 N - 1 까지인 이유는 4등분으로 하기 위함이다.

N까지로 설정하면 r4가 실행 안 되는 경우가 있음.

BOJ portableangel님의 코드의 아이디어를 참고하였다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int N = 0, ans = 0;
 
vector<int> v;
 
int simulation(int a, int b, int c)
{
    int r1 = 1, r2 = 1, r3 = 1, r4 = 1;
 
    for (int i = 0; i < N; i++)
        if (i <= a) r1 *= v.at(i);
        else if (i <= b) r2 *= v.at(i);
        else if (i <= c) r3 *= v.at(i);
        else r4 *= v.at(i);
    
    return r1 + r2 + r3 + r4;
}
 
int main(void)
{
    int n = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &n);
 
        v.push_back(n);
    }
 
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            for (int k = j + 1; k < N - 1; k++) // N까지가 아니라, N - 1까지이다.
                ans = max(ans, simulation(i, j, k));
 
    printf("%d\n", ans);
 
    return 0;
}