백준 5883 아이폰 9S Python

🐸 문제 정보

5883번: 아이폰 9S

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

12.32m

 

📝 풀이

처음에 2차원 DP로 풀어야하나 했으나(LCS..?) LCS 개념과는 약간 다른 것 같아 구현으로 풀어봤더니 풀렸다.

구현으로 풀면 간단하게 풀 수 있는 문제였다.

 

1. set을 이용해서 용량 종류 파악하기
2. 용량 종류를 하나씩 빼서 새로운 배열을 할당하고, 해당 배열에서 연속된 용량의 길이 구하기
   • 마지막에 정답을 한 번 더 갱신해주는 것이 중요하다.

아래는 처음 제출 때 틀려서 찾은 반례이다.

4
1
1
1
3

# answer: 3

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = [int(input().rstrip()) for _ in range(n)]
num_type = set(nums)
res = 1

for type in num_type:
    arr = [num for num in nums if num != type]
    temp = 1
    for i in range(1, len(arr)):
       if arr[i] != arr[i - 1]:
           res = max(res, temp)
           temp = 1
       else:
           temp += 1
    res = max(res, temp)

print(res)