반응형
https://www.acmicpc.net/problem/2229
2229번: 조 짜기
알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는
www.acmicpc.net
[ 문제풀이 ]
1. dp [ i ] 에는 i번 학생까지의 조가 잘 짜여진 정도의 최댓값을 저장합니다.
2. 다음과 같은 점화식을 세웁니다.
dp [ i ] = max(dp [ i ], dp [ j - 1 ] + Max - Min)
3. 이때, Max와 Min은 j ~ i번 학생들의 점수 최댓값과 최솟값입니다.
[ 소스코드 ]
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 | #include<iostream> using namespace std; int N; int arr[1001]; int dp[1001]; //i번 학생까지 잘 짜여진 정도의 최댓값 int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &arr[i]); } for (int i = 2; i <= N; i++) { int Max = arr[i]; int Min = arr[i]; for (int j = i - 1; j > 0; j--) { Max = max(Max, arr[j]); Min = min(Min, arr[j]); dp[i] = max(dp[i], dp[j - 1] + Max - Min); //j ~ i 까지의 최댓값과 최솟값의 차와 dp[j - 1]의 합 } } printf("%d", dp[N]); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++) (0) | 2022.11.05 |
|---|---|
| [ 백준 ] 1577번 - 도로의 개수 (C++) (0) | 2022.11.04 |
| [ 백준 ] 2157번 - 여행 (C++) (0) | 2022.11.02 |
| [ 백준 ] 2666번 - 벽장문의 이동 (C++) (0) | 2022.11.01 |
| [ 백준 ] 2302번 - 극장 좌석 (C++) (0) | 2022.10.31 |