[2020모각코] 3회차 2021.01.05

동적 계획법(Dynamic Programming)이란

주어진 문제를 작은 여러 개의 문제로 나누어서 풀 때 같은 문제들을 반복해서 푸는 경우가 생긴다. 그런 경우 그 문제들을 매번 재계산 하는것이 아니라 값을 저장해 두었다가 재사용하는 기법이다.

 

이 문제를 해결하기 위해선 이전 값을 1로 만드는데 필요한 횟수를 저장하는 것이 중요하다.

문제를 보면 정수 x에 사용할 수 있는 연산 중 하나가 1을 빼는 연산이다. 따라서 bottom-up방식으로 문제를 해결해 나가야 한다고 생각하였다.  a라는 배열을 만들어 1로 만드는데 필요한 연산의 횟수를 저장하여 문제를 해결하였다.

 

sum이라는 변수를 통해 연속된 숫자의 합을 저장하였다. sum이 0보다 작게 되는 경우 그 부분순열을 연속합을 최대로 만들어 줄 수 없기 때문에 그 다음 값으로 새로운 부분순열을 만들어 주었다. sum1 변수에는 이전까지의 최대 연속합을 저장해 주었다. cnt를 통해 모든 입력값이 음수인 경우를 예외처리해 문제를 해결하였다.