[백준] 2491 수열 (실버4) / DP(다이나믹 프로그래밍)

문제요약

나의 코드 및 설명

• 입력받은 수를 리스트에 저장하고, for문을 통해 인덱스 1의 수부터 하나하나 살펴본다.
  만약 이전의 수보다 크거나 같다면 big_cnt에 1을 추가한다. 이 때, big_cnt 값이 ans보다 크다면, ans를 big_cnt로 갱신한다. 만약, 이전의 수보다 크거나 같지 않다면 big_cnt를 1로 초기화한다.
  이번엔 이전의 수보다 작거나 같은지 확인하기 위해 새로운 if문을 수행한다. 동작 방식은 크거나 같은지 확인하는 if문과 동일하다. 
  이 때, small_cnt의 값을 갱신하기 위해 ans 변수에 접근하게 되는데, 이를 통해 연속되는 크거나 같은 수의 개수, 연속되는 작거나 같은 수의 개수의 최댓값이 ans에 저장되게 되고, ans만 출력하게 되면 문제를 해결할 수 있다.   

n = int(input())
num_list = list(map(int, input().split()))

ans = 1
big_cnt = 1
small_cnt = 1
for i in range(1, len(num_list)):
    #커지는 수 
    if num_list[i] >= num_list[i-1]:
        big_cnt+=1
        if ans < big_cnt:
            ans = big_cnt
    else: 
        big_cnt = 1
    #작아지는 수
    if num_list[i] <= num_list[i-1]:
        small_cnt+=1
        if ans < small_cnt:
            ans = small_cnt
    else:
        small_cnt = 1

print(ans)

다른 코드 및 설명 - DP(다이나믹 프로그래밍)

• dp1 : 몇 개의 수가 연속적으로 증가하는지 저장
  dp2: 몇 개의 수가 연속적으로 감소하는지 저장

n = int(input())
num_list = list(map(int, input().split()))

dp1 = [1 for _ in range(n)] #가장 긴 증가하는 수열
dp2 = [1 for _ in range(n)] #가장 긴 감소하는 수열

for i in range(1, n):
    if num_list[i-1] <= num_list[i]:
        dp1[i] = dp1[i-1] + 1
    if num_list[i-1] >= num_list[i]:
        dp2[i] = dp2[i-1] + 1

print(max(max(dp1), max(dp2)))

피드백

다이나믹 프로그래밍이 숙달되지 않아서 문제를 보고 단순 구현하는 방법밖에는 생각하지 못했다. 다이나믹 프로그래밍의 이론에서처럼 sub-problem 을 해결하고 필요시에 그 결과를 다시 활용하는 방식을 통해 문제를 해결함으로써 다이나믹 프로그래밍의 이론을 다시 복습하고 활용해볼 수 있었던 좋은 경험이 되었다. 앞으로도 더욱 숙달하도록 하자.