알고리즘
-
알고리즘 2020. 7. 17. 15:55
Dynamic Programming을 이용한, 아주 간단한 연속합을 구하는 문제이다. 시작 index인 0에 대하여서는 DP[0]=arr[0]값을 설정해 준 뒤, i=1부터 입력받은 정수 n까지는 for문을 탐색하며 연속합을 갱신한다. DP[i-1]+arr[i] 값, 즉 이전 index까지의 최대 연속합에 현재 index의 value인 arr[i]값을 더한 값과, 현재 index의 value인 arr[i]값 중 더 큰 값을 DP[i]값으로 설정한다. DP[0]=arr[0]; for(i=1;ib ? a : b; } int DP[100001] = {0,}; int main(){ int arr[100001]={0,}; int i,cnt,n; int result; scanf("%d",&cnt); for(i=0;i
-
알고리즘 2020. 7. 17. 15:21
Dynamic Programming문제이다. 이전에 풀었던 가장 긴 증가하는/감소하는 수열 문제를 응용하여 어렵지 않게 풀어낼 수 있었다. 입력받은 수열에 대하여 for문을 수행하며, 1. 현 index에서의 arr[i]의 value가 앞선 index의 value보다 큰 값을 가지고 있고 2. DP[i]의 value가 앞선 index j의 value와 작거나 같다면, DP[i]의 값을 1 증가시킨다 for(i=0;ii;j--){ if(arr[i]>arr[j] && decreasingDP[i]b ? a : b; } int increasingDP[1001] = {0,}; int decreasingDP[1001] = {0,}; int main(){ int arr[1001]={0,}; int i,cnt,n,ma..