[BOJ/Silver 2] 백준 30971 육회비빔밥(C++)

문제 링크

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

 

문제

진주 나들이를 온 보선이는 배가 너무 고파 육회비빔밥을 먹기 위해 진주 대안동에 갔다. 그런데 이게 웬 떡? 육회비빔밥 시식 행사가 진행 중이었다. 대식가이자 미식가인 보선이는 육회비빔밥을 감칠맛이 최대한 나게끔 전부 먹으려고 한다. 하지만 전부 먹으려고 하니 아무리 뻔뻔한 보선이라도 시식대 직원의 눈치가 조금 보이기 시작했다. 그래서 각 시식대의 정보를 파악해서 전략적으로 먹기로 했다.

육회비빔밥 시식대는 총 𝑁개가 있다. 각 시식대에는 육회비빔밥 한 그릇과 직원 1명이 있으며, 육회비빔밥의 단맛과 짠맛 그리고 그곳에 있는 직원이 눈치 주는 정도는 수치로 나타낼 수 있다. 보선이는 육회비빔밥이 남아 있는 시식대 중 하나를 골라서 갈 수 있으며, 한 시식대에 갈 때마다 그곳에 있는 육회비빔밥은 무조건 다 먹어야 한다.

보선이가 𝑖번째로 간 시식대에 있는 육회비빔밥의 단맛과 짠맛을 각각 𝐴𝑖, 𝐵𝑖라고 하였을 때, 보선이가 느낄 수 있는 총 감칠맛은 다음과 같이 정해진다.

 또한, 보선이는 첫 번째로 간 시식대에서는 눈치를 받지 않으나 두 번째로 간 시식대부터는 눈치를 받게 된다. 구체적으로, 𝑖번째로 간 시식대에 있는 직원이 눈치 주는 정도를 𝐶𝑖라고 하였을 때, 𝑖(𝑖 ≥ 2)번째로 간 시식대에서 보선이가 눈치 받는 정도는 𝐶𝑖−1 × 𝐶𝑖가 된다. 하지만 보선이는 𝐾만큼의 뻔뻔함의 정도를 지니고 있어서, 눈치 받는 정도가 𝐾 이하라면 아랑곳하지 않고 그곳에 있는 육회비빔밥을 먹는다. 그렇지만 눈치 받는 정도가 𝐾를 넘게 되면 그곳에 있는 육회비빔밥을 먹지 못하고 시식을 중단하게 된다.

위와 같은 조건들을 고려해서 보선이가 육회비빔밥 𝑁그릇을 다 먹었을 때 느낄 수 있는 총 감칠맛의 최댓값을 구해보자.

 

입력

첫 번째 줄에는 시식대의 개수 𝑁, 보선이의 뻔뻔함의 정도 𝐾가 공백으로 구분되어 주어진다. (2 ≤ 𝑁 ≤ 10; 1 ≤ 𝐾 ≤ 100)

두 번째 줄에는 각 시식대에 있는 육회비빔밥의 단맛 𝐴1, …, 𝐴𝑁이 공백으로 구분되어 주어진다. (1 ≤ 𝐴𝑖 ≤ 10)

세 번째 줄에는 각 시식대에 있는 육회비빔밥의 짠맛 𝐵1, …, 𝐵𝑁이 공백으로 구분되어 주어진다. (1 ≤ 𝐵𝑖 ≤ 10)

네 번째 줄에는 각 시식대에 있는 직원의 눈치 주는 정도 𝐶1, …, 𝐶𝑁이 공백으로 구분되어 주어진다. (1 ≤ 𝐶𝑖 ≤ 10)

입력으로 주어지는 모든 수는 정수이다.

 

출력

첫 번째 줄에 보선이가 육회비빔밥 𝑁그릇을 다 먹었을 때 느낄 수 있는 총 감칠맛의 최댓값을 출력한다. 만약 육회비빔밥 𝑁그릇을 다 먹을 수 없다면 –1을 출력한다.

 

예제 입력 1

3 6
10 5 2
2 10 5
2 3 1

예제 출력 1

125

예제 입력 2

3 8
1 1 1
2 2 2
3 3 3

예제 출력 2

-1

 

보선이는 어떤 순서로 먹어도 눈칫밥을 먹어 체하고 말 것이다...

 

노트

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.

 

알고리즘 분류

• 백트래킹

 

풀이

첫 번째 시식대부터 N번째 시식대까지 모두 탐색하면서 해당 시식대를 처음으로 골랐다고 한다.

그럼 다음 시식할 시식대를 고르는데, 여기서 이전 C와 고를 시식대의 C의 곱이 K 이하여야 한다.

눈치를 안 보면서 N개의 시식대를 전부 탐색하면 감칠맛의 최댓값을 기록한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 11
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, K;
int A[MAX], B[MAX], C[MAX];
bool Visited[MAX];
int Answer = -1;

void input() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }
}

void dfs(int Depth, int PrevA, int PrevC, int Sum) {
    if (Depth == N) {
        Answer = max(Answer, Sum);
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!Visited[i] && (PrevC * C[i] <= K)) {
            Visited[i] = true;
            dfs(Depth + 1, A[i], C[i], Sum + (PrevA * B[i]));
            Visited[i] = false;
        }
    }
}

void settings() {
    for (int i = 0; i < N; i++) {
        Visited[i] = true;
        dfs(1, A[i], C[i], 0);
        Visited[i] = false;
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}