-
해당 문제는 DP를 이용하여 간단하게 해결하였다.
https://www.acmicpc.net/problem/1912
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201912
해당 문제는 N 개의 정수로 이루어진 임의의 수열이 주어지면 이 수열 중에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제다.
조건
수는 한 개 이상 선택해야 한다.
해당 문제는 DP를 이용해서 처음 arr 배열에 임의의 수열을 입력받으면 arr[0]=dp[0] 을해주고 이후 1부터 N까지 반복문을 돌리면서 arr[i]와 arr[i]+dp[i-1] 중에서 최댓값을 dp에 넣으면서 값을 비교해나가면 된다. 이후 dp 배열을 정렬해 주고 가장 마지막 값을 출력해 주면 해결 가능한 문제다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 11047 동전 0 JAVA (0) 2021.11.05 Baekjoon 9465 스티커 JAVA (0) 2021.11.05 Baekjoon 1049 기타줄 JAVA (0) 2021.11.05 Baekjoon 1002 터렛 JAVA (0) 2021.11.05 Baekjoon 11399 ATM JAVA (0) 2021.11.05 댓글