A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 12 + 21 연속합이 33으로 최대
- 1 <= n <= 100,000
-1,000 <= Ai <= 1,000
2. 접근방법
- 연속합이 최대
- 어느지점에서 새로운 연속이 생길까?
- 이전 까지의 합 보다 현재의 값이 더 크면 새로운 연속의 시작
- d[i] = max(d[i], d[i-1] + a[i])
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
0
0
0
0
0
0
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
0
0
0
0
0
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
0
0
0
0
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
0
0
0
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
15
0
0
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
15
21
0
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
15
21
-14
0
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
15
21
-14
12
0
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
15
21
-14
12
33
0
a
10
-4
3
1
5
6
-35
12
21
-1
d
10
6
9
10
15
21
-14
12
33
32
3. 시간복잡도
- n
4. 회고
- 값의 범위가 -1000 <= Ai <= 1000 으로 음수가 됨을 망각함.
- 첫번째 실수, d의 값을 0으로 시작함..
첫번째 입력값이 음수이면 d는 음수가 아니라 0으로 시작하게 됨
- 두번째 실수, ans의 값을 0으로 초기화함...
집합의 모든 수가 음수 이면 정답은 0이 되어버림
소스코드
#include<iostream>
using namespace std;
int n, temp, d = -1001, ans = -1001;
int main(void){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> temp;
if (temp < d + temp) d = d + temp;
else d = temp;
if (ans < d) ans = d;
}
cout << ans << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
A = {10, 30, 10, 20, 20, 10} 가장 긴 감소하는 부분 수열의 최대 길이는 3
2. 접근방법
- LIS와 같음
3. 시간복잡도
- n^2
4. 회고
소스코드
#include<iostream>
using namespace std;
int n, d[1001], a[1001], ans = 0;
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++){
d[i] = 1;
for (int j = 0; j < i; j++)
if (a[i] < a[j] && d[i] < d[j] + 1)
d[i] = d[j] + 1;
if (ans < d[i]) ans = d[i];
}
cout << ans << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
#include<iostream>
using namespace std;
int n, d[1001], a[1001], ans = 0;
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++){
d[i] = a[i];
for (int j = 0; j < i; j++)
if (a[j] < a[i] && d[i] < d[j] + a[i])
d[i] = d[j] + a[i];
if (ans < d[i]) ans = d[i];
}
cout << ans << "\n";
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
#include<iostream>
using namespace std;
int t, n, d[2][100002];
int max(int a, int b){
return ((a < b) ? b : a);
}
int main(void){
cin >> t;
while (t--){
cin >> n;
int a, b;
for (int i = 0; i < 2; i++)
for (int j = 1; j <= n; j++)
cin >> d[i][j];
for (int i = 2; i <= n; i++){
d[0][i] += max(d[1][i - 1], d[1][i - 2]);
d[1][i] += max(d[0][i - 1], d[0][i - 2]);
}
cout << max(d[0][n], d[1][n]) << "\n";
}
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
단순히 모든 정점을 방문한다고 생각해서 friends[i][k] == 'Y' && frineds[k][j] == 'Y' 라고 하면
플로이드에서 0 -(N)-> 0 -(Y)-> 1 인 경우 친구가 아니라고 판단하게 됨
또한, 0 -(Y)-> 1 -(Y)-> 0 인경우는 friends[0][0] 을 친구로 만들어 버림
friends 를 업데이트 하게 되면 A-B-C-D 에서 A-D가 친구로 판단 하기 때문에 다른 친구관계를 저장할 다른 배열이 필요함
- 3가지 경우로 나눠야 함
ⅰ) A -(N)-> A -(Y)-> B 인 경우
i == k && friends[k][j] == 'Y'
ⅱ) A -(Y)-> B -(N)-> B 인 경우
k == j && friends[i][k] == 'Y'
ⅲ) 일반적인 경우 A -(Y)-> B -(Y)-> C
friends[i][k] == 'Y' && friends[k][j] == 'Y'
※ 나머지
0 -(Y)-> 1 -(Y)-> 0 으로 돌아오는 경우는 새로 만들어 주는 배열에서 친구관계를 셀때 빼면됨
플로이드는 경로가 출발, 도착 보다 뒤에 바뀌기 때문에 책처럼 풀 수 없음
0 -> 1 -> 2 다음엔 0 -> 1 -> 3 ... 1 -> 1 -> 3 이런 순이기 때문에 한 정점에서 시작하는 모든 친구를 셀 수 없음
- dfs 는
1
0 < |
2 - 3
인 경우에 0 - 1 - 2 순으로 방문하면 정점 2는 방문 했기 때문에 더이상 방문을 하지 못함
하지만 최단거리(친구 2단계) 에서는 0 - 2 - 3 으로 0과 3이 친구가 될 수 있음
- bfs 는 깊이(친구 2단계)를 지정해주면 풀 수있음
소스코드 : 플로이드
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class FriendScore{
public:
int highestScore(vector <string> friends){
int ans = 0; int n = friends[0].size();
vector<vector<bool> > map(n, vector<bool>(n, false));
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((i == k && friends[k][j] == 'Y') || (k == j && friends[i][k] == 'Y') || (friends[i][k] == 'Y' && friends[k][j] == 'Y'))
map[i][j] = true;
for (int i = 0; i < n; i++){
int temp = 0;
for (int j = 0; j < n; j++){
if (i != j && map[i][j]) temp++;
}
if (ans < temp) ans = temp;
}
return ans;
}
};
소스코드 : bfs
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
class FriendScore{
public:
int highestScore(vector <string> friends){
int ans = 0;
vector<bool> check;
queue<pair<int, int> > q;
for (int i = 0; i < friends[0].size(); i++){
check = vector<bool>(friends[0].size(), false);
check[i] = true;
q.push(make_pair(i, 0));
int temp = 0;
while (!q.empty()){
int now = q.front().first;
int deep = q.front().second;
q.pop();
for (int j = 0; j < friends[0].size(); j++){
if (deep < 2 && !check[j] && friends[now][j] == 'Y'){
check[j] = true;
q.push(make_pair(j, deep + 1));
temp++;
}
}
}
if (ans < temp) ans = temp;
}
return ans;
}
};
