Baekjoon_2559_수열, Baekjoon_2491_수열

 

2559번: 수열

Baekjoon_2559_수열

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

 

 

이때, 온도의 합이 가장 큰 값은 21이다. 

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며, 

 

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

 

해결방법

- 슬라이딩 윈도우,  처음에 반복문으로 sum을 매번 구했더니 시간초과가 났음

- 이후에는 최대값 변수 선언할 때 아무생각없이 0 으로 해서 틀렸당, 아래처럼 했었어야지

# 초기화를 맨 처음 윈도우의 누적합으로 설정하자
maxV = temp[K-1]

 

실패한 코드

N, K = map(int, input().split())
temp = list(map(int, input().split()))

maxV = 0
for i in range(N-K+1):
    if sum(temp[i:i+K]) > maxV:
        maxV = sum(temp[i:i+K])

print(maxV)

 

정답 코드

N, K = map(int, input().split())
temp = list(map(int, input().split()))

# 누적합 구하기
for i in range(1, N):
    temp[i] += temp[i-1]

st = 0
en = K
# 초기화를 맨 처음 윈도우의 누적합으로 설정하자
maxV = temp[K-1]
while en < N:
    if temp[en] - temp[st] > maxV:
        maxV = temp[en] - temp[st]
    st += 1
    en += 1

print(maxV)

 

 

 

 

 

2491번: 수열

Baekjoon_2491_수열

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

 

해결방법

- 또 maxV 초기값을 아무생각없이 0 으로 했음, 가장 짧은 길이는 1이어야 해

 

코드

N = int(input())

nums = list(map(int, input().split()))

cnt1 = 1
cnt2 = 1
i = 1
maxV = 1
while i < N:
    # 오름차순
    if nums[i - 1] <= nums[i]:
        cnt1 += 1
        if cnt1 > maxV:
            maxV = cnt1
    else:
        cnt1 = 1

    # 내림차순
    if nums[i - 1] >= nums[i]:
        cnt2 += 1
        if cnt2 > maxV:
            maxV = cnt2
    else:
        cnt2 = 1
    i += 1

print(maxV)

 

 

 

콜드브루를 벌컥벌컼 마셨더니 잠이 안오네,,, 그래도 문제는 더 풀기 싫다. 

월말평가 한번에 통과하고 싶다..! 시험 못봐도 월요일엔 진짜진짜 아무 생각도 안하고 재밌게 놀거야ㅠ