[BOJ/Silver 2] 백준 30804 과일 탕후루(C++)

문제 링크

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

30804번: 과일 탕후루

 

문제

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1, S2, ⋯, SN번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a개, 뒤에서 b개의 과일을 빼면 Sa+1, Sa+2, ⋯, SN−b−1, SN−b번 과일, 총 N − (a + b)개가 꽂혀있는 탕후루가 됩니다. (0 ≤ a, b; a + b < N)

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

 

입력

첫 줄에 과일의 개수 N이 주어집니다. (1 ≤ N ≤ 200,000)

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S1, ⋯, SN이 공백으로 구분되어 주어집니다. (1 ≤ Si ≤ 9)

 

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

 

예제 입력 1

5
5 1 1 2 1

예제 출력 1

4

 

과일을 앞에서 1개, 뒤에서 0개의 과일을 빼면 남은 과일은 1, 1, 2, 1번 과일이 꽂혀있는 탕후루가 됩니다. 과일의 개수는 4개입니다.

예제 입력 2

3
1 1 1

예제 출력 2

3

 

탕후루가 이미 두 종류 이하의 과일로만 이루어져 있습니다.

예제 입력 3

9
1 2 3 4 5 6 7 8 9

예제 출력 3

2

 

과일을 앞에서 3개, 뒤에서 4개의 과일을 빼면 남은 과일은 4, 5번 과일이 꽂혀있는 탕후루가 됩니다. 과일의 개수는 2개입니다.

 

알고리즘 분류

• 두 포인터

 

풀이

먼저 Left, Right 두 포인터를 0으로 초기화한다.

그리고 먼저 Right을 1씩 증가시키면서 해당하는 과일의 종류를 확인한다.

과일의 종류가 2가지를 넘으면 앞쪽의 과일을 하나씩 제거하면서 Left를 1씩 증가시켜 과일의 종류가 2가지가 넘지 않도록 만든다.

나만 어렵나 이거..?

 

참고

백준 30804 과일 탕후루 Java

 

코드

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

using namespace std;
int N, S;
vector<int> Fruits;
int Fruit_Count[MAX];

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S;
        Fruits.push_back(S);
    }
}

int DFS(int L, int R, int Count, int Answer, int Kind) {
    if (R >= N) {
        return Answer;
    }

    if (Fruit_Count[Fruits[R]] == 0) {
        Kind++;
    }
    Count++;
    Fruit_Count[Fruits[R]]++;

    while (Kind > 2) {
        Count--;
        Fruit_Count[Fruits[L]]--;
        if (Fruit_Count[Fruits[L]] == 0) {
            Kind--;
        }
        L++;
    };

    Answer = max(Answer, Count);

    return DFS(L, R + 1, Count, Answer, Kind);
}

void find_Answer() {
    cout << DFS(0, 0, 0, 0, 0) << "\n";
}

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

    return 0;
}