Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 2670 연속부분 최대 곱
문제
N개의 실수가 있을 때 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 출력해라.
입력 및 출력
첫 번째 줄: 나열될 양의 실수들의 개수 N 두 번째 줄 ~ 마지막 줄: 실수
Dynamic Programming
- 재귀와 유사
- 하지만 재귀를 사용하면 동일한 문제가 여러번 반복되어 비효율적
- 동적 프로그래밍은 큰 문제를 작은 문제로 쪼개 답을 저장해두고 계속 재활용
- 하나의 문제를 한 번만 풀도록 하는 알고리즘
DP 사용 조건
- Overlapping Subproblems
- 동일한 문제들이 반복되어야 함
- Optimal Substructure
- 부분 문제의 최적 결과 값을 사용해 전채 문제의 최적 결과를 낼 수 있어야 함
구현 방식
- Bottom-up
- 작은 문제부터 구해가는 방식
- Top-down
- 큰 문제를 풀 때 작은 문제가 아직 해결되지 않은 상태라면 작은 문제를 먼저 해결하는 방식
코드
해결 방식
- arr[i] 값 dp[i-1]*arr[i] 값 비교
- dp[i-1]은 arr[i]이전의 수들의 곱이 최대가 되는 부분
- dp[i-1]은 arr[i]이전의 수들의 곱이 최대가 되는 부분
if) arr[i] < dp[i-1] * arr[i]
- arr[i] = dp[i-1] * arr[i]
else if) arr[i] > dp[i-1] * arr[i]
- 변경 x
