알고리즘 문제풀이
[Programmers] 프로그래머스 Lv.3 연속 펄 부분 수열의 합 문제풀이(C++)
도리컴
2023. 9. 7. 00:05
반응형
누적합 및 DP 개념 이용한 문제 / Lv.3정도까지의 난이도는 아닌거 같았음
처음에 시행착오 겪고 비교적으로 바로 해답이 떠올랐음
근데 dp[500001] 변수를 int로 선언해서 TC 3갠가 틀리면서 시간 엄청 까먹음....ㅠㅜ
변수선언 할 때 생각했나요?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <string>
#include <vector>
using namespace std;
/*
<문제>
수열 sequence가 주어짐
이 열의 부분수열을 추출해서 거기 펄스수열 각 원소 곱했을 때, 합이 가장 큰 경우의 합 리턴
펄스수열 : -1, 1이 번갈아가면서 나오는 수열(무엇이 먼저인지는 상관없음)
sequence 길이 <= 50만
-10만 <= sequence 각 원소 <= 10만 / 정수
<풀이>
1. 모두 해보면? / 그냥 너무 당연하게 시간초과
2. 재귀를 이용?
전체에서의 가장 큰경우 = (가장 마지막원소 빼고 했을 때 가장 큰 경우) 랑 (전체로 했을 때 합) 중에 더 큰거
-> 시간초과 / 뭔가 그럴 것 같았음
3. DP - 누적합 이용 떠오름
<시간>
O(sequence 길이)
*/
long long dp[500001]; //dp[n] : [0]~[n]까지 연속펄스부분수열합
//r_dp[500001] //r_dp[n] : [0]~[n]까지 반대펄스수열 합인데, 펄스 수열이 반대인경우 -> dp[n]*(-1)일 텐데?
//잠만 그러면, 그냥 절댓값 큰 거 고르면 되는거 같은데
long long solution(vector<int> sequence) {
long long answer;
dp[0]=sequence[0]*(-1); //-1로 시작하는 펄스라 가정
int tmp=1;
for(int i=1; i<sequence.size(); i++){
dp[i] = dp[i-1] + (tmp*sequence[i]);
tmp*=-1;
}
//-1로 시작하는 연속펄스 적용, dp[] 저장 완료
//dp에서 최대값과 최소값의 차가 정답
long long maxx = -60000000000;
long long minn = 60000000000;
dp[sequence.size()]=0; //부분수열이 원소 하나로 이루어져 있을 때를 의미
for(int i=0; i<=sequence.size(); i++){
if(maxx < dp[i]) maxx = dp[i];
if(minn > dp[i]) minn = dp[i];
}
answer = maxx-minn;
if(answer<0) answer*=(-1);
return answer;
}
|
cs |
반응형