백준 9461 파도반 수열, 연속합 1912

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

 

 

EXPLANATION

6번째 삼각형부터 바로 이전 삼각형과 5번 이전 삼각형의 넓이랑 같다.

3 = 2 + 1

4 = 3 + 1

5 = 4 + 1

7 = 5 + 2

.

.

.

 

CODE

#include <iostream>

using namespace std;

long long P[101] = {0,1,1,1,2,2};    //for [1, N]

int main(void){
	int T;
	cin >> T;
	for(int i = 0; i < T; i++){
		int N;
		cin >> N;
		for(int i = 6; i <= N; i++){
			P[i] = P[i - 1] + P[i - 5];
		}
		cout << P[N] << "\n";	
	}

	return 0;
}

 

 

 

 

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

 

 

EXPLANATION

 

수열에서 각 index i마다

이 index 이전의 어떤 index부터 이 index까지 연속해서 더했을 때 가장 커지는 값,

즉, 그 index부터 내려가면서 연속해서 더했을 때 가장 커지는 값을 구한다.

그것을 dp[i]라고 하자.

 

dp[i]를 구하는 법:

dp[0]은 어차피 자신보다 앞에 차례가 없으니 그대로 dp[0] = arr[0]

dp[1]부터는 자신의 원소 혼자만 더한 것과, 이전의 어떤 index로 부터 직전의 index까지의 연속해서 더했을 때 가장 커지는 값 dp[i - 1]에 자신의 원소를 더한 것을 비교해서 더 큰 값으로 갱신.

 

그리고 그 dp[i]들 중에서 최댓값을 구하면된다.

 

 

ex)

10 -4 3 1 5 6 -35 12 21 -1

 

index i	arr[i]	dp[i] = (index i 부터 연속해서 더했을 때 가장 큰 값)
0	10	10
1	-4	6
2	3	9
3	1	10
4	5	15
5	6	21
6	-35	-14
7	12	12
8	21	33
9	-1	32

dp[i]의 최댓값 dp[8]의 33이 답.

 

 

 

CODE

#include <iostream>
#include <algorithm>
#define MAX 100000
using namespace std;
int arr[MAX], dp[MAX]={};
int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>arr[i];
    }
    for(int i=0; i<n; i++) {
        dp[i]=max(arr[i], dp[i-1]+arr[i]);    //arr[i]자신의 원소 혼자만 더한 것과, 이전의 어떤 index로 부터 직전의 index까지의 연속해서 더했을 때 가장 커지는 값 dp[i - 1]에 자신의 원소를 더한 것을 비교해서 더 큰 값으로 갱신  
    }
    sort(dp, dp + n);    //dp[i]를 오름차순으로 나열하면 맨 마지막이 최댓값
    cout << dp[n-1] << "\n";
   
    return 0;
}