백준 30804번: 과일탕후루

본 포스팅은 문제의 풀이 보단 작성자의 개인적인 정리에 가깝습니다.
그냥 이 사람은 이렇게 풀었구나 정도로 봐주시면 감사하겠습니다

 

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

 

문제

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

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 𝑎개, 뒤에서 𝑏개의 과일을 빼면 𝑆𝑎+1,𝑆𝑎+2,⋯,𝑆n−𝑏−1,𝑆n−𝑏번 과일, 총 𝑁−(𝑎+𝑏)개가 꽂혀있는 탕후루가 됩니다. (0≤𝑎,𝑏;𝑎+𝑏<𝑁)
이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

 

입력

첫 줄에 과일의 개수 𝑁이 주어집니다. (1≤𝑁≤200000)

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

 

출력

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

예제 입력1

5
5 1 1 2 1

예제 출력1

4

예제 입력2

3
1 1 1

예제 출력2

3

풀이

import sys

def get_possible_combi(lis):
    check = set()
    for i in lis:
        check.add(i)
    if(len(check)<3):
        return True, len(lis)
    
    combi = set()
    
    for i in range(len(lis)-1):
        if(lis[i]==lis[i+1]):
            continue
        elif(lis[i]<lis[i+1]):
            combi.add((lis[i],lis[i+1]))
        else:
            combi.add((lis[i+1],lis[i]))
    return False, combi

def get_result(lis,combis):
    max_cnt = 0
    # print(combis)
    for combi in combis:
        cur_best=0
        cnt=0
        # print("현재 combi",combi)
        for i in range(len(lis)):
            data = lis[i]
            # print("     data:",data, end=" ")
            if(data in combi):
                cnt+=1
            else:
                cnt=0
            cur_best = max(cnt,cur_best)
            # print("     cnt:",cnt)
        max_cnt=max(max_cnt,cur_best)
    return max_cnt


_ = int(sys.stdin.readline())

lis = list(map(int,sys.stdin.readline().split()))

status, value = get_possible_combi(lis)
if(status):
    pass
else:
    value = get_result(lis,combis=value)
print(value)

 

답은 위와 같습니다.

다양한 방법들이 있겠으나 저는 우선 가능한 조합을 찾았습니다. 1,2와 2,3 같이 말입니다.

가능한 조합은 두 숫자가 붙어있는 경우가 가능한 조합입니다.

1, 4, 5와 같은 경우가 있다고하면 1,4와 4,5는 가능하지만 1,5는 불가능합니다. 이런 것들을 우선 체크했습니다.

 

그 후로 가능한 모든 조합들을 하나씩 사용하여 list를 순회하며 개수를 카운트하면 됩니다