(Python/🥈3)백준 알고리즘 15779번: Zigzag

 

문제 바로가기 

 

문제:

어떤 수열에서, 연속된 3개의 수를 보았을 때, 그 수가 단조증가 수열이거나, 단조감소 수열인 경우가 없으면 이 수열을 "지그재그 수열" 이라고 말한다. 좀 더 정확하게는, 길이 N의 수열 A가 모든 1 이상 N-2 이하의 자연수 i에 대해서, Ai ≤ Ai+1 ≤ Ai+2도 만족하지 않고, Ai ≥ Ai+1 ≥ Ai+2도 만족하지 않으면, A는 지그재그 수열이다. 길이 N의 수열 A가 주어졌을 때, A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라. 길이 M의 B가 길이 N인 A의 연속된 부분 수열이라는 것은, 어떤 i가 존재 해서, B1 = Ai, B2 = Ai+1, ..., BM = Ai+M-1 인 것을 말한다.

입력:

입력은 두 줄로 이루어져 있다. 첫째 줄에는 수열의 길이 N이 주어진다. 둘째 줄에는 공백으로 구분된 N개의 정수가 주어진다. i번째 수는 Ai를 의미한다.

 

출력:

A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라.

 

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(sys.stdin.readline())

def solution(lst):
    if len(lst) >= 3:
        for i in range(len(lst) - 2):
            if (lst[i] <= lst[i + 1] <= lst[i + 2]) or (lst[i] >= lst[i + 1] >= lst[i + 2]):
                return False
    return True


num = list(map(int,sys.stdin.readline().rsplit(" ")))
res = 0
for i in range(len(num)):
    for j in range(i+2,len(num) +1):
        temp = num[i:j]
        if solution(temp):
            res = max(res, len(temp))

print(res)

이건 70점 받은 풀이다.

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


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

lst = list(map(int,sys.stdin.readline().rsplit(" ")))
dp = [2] * N
for i in range(N-2):
    if (lst[i] <= lst[i + 1] <= lst[i + 2]) or (lst[i] >= lst[i + 1] >= lst[i + 2]):
        continue
    dp[i] = dp[i-1] + 1

print(max(dp))

dp에 저장하기로 했다.

N이 무한히 커지면 시간초과땜에 안 뜬다고 생각했다.