티스토리 뷰
문제 요약
- 알고리즘 분류: dp, 동적 계획법
- 난이도: Medium
- 문제내용:
- 정수 n이 주어지면 k개의 양의 정수의 합(k > = 2)으로 나누고 그 정수의 곱을 최대화한다.
- 사이트 주소: https://leetcode.com/problems/integer-break/description/
문제풀이
이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 DP로 풀어야 통과가 되는 문제이다. DP에 대한 자세한 설명은 아래글로 확인해보면 된다.
https://jih3508.tistory.com/89
문제 접근방법
dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다. 일단 각 최대로 나오는것 먼저 확인 해보자.
2 = 1 × 1 = 1
3 = 1 × 2 = 2
4 = 2 × 2 = 4
5 = 2 × 3 = 6
6 = 3 × 3 = 9
7 = 3 × 4 = 12
8 = 2 × 3 × 3 = 18
9 = 3 × 3 × 3 = 27
10 = 3 × 3 × 4 = 36
11 = 2 × 3 × 3 × 3 =54
1 부터 5나 6까지 했으면 N // 2 × (N // 2 + N % 2)이렇게 되었지만 8부터는 다르다. 그래서 다시 아래를 확인 해보자
1 = 1
2 = 1 × 1 = 1
3 = 1 × 2 = 2
4 = 2 × 2 = 4
5 = 2 × 3 = 6
6 = 3 × 3 = 9
7 = 3 × 4 = 12
8 = 2 × 3 × 3 = 2 × dp[6] = 18
9 = 3 × 3 × 3 = 3 × dp[6] = 27
10 = 3 × 3 × 4 = 3 × dp[7] = 36
11 = 2 × 3 × 3 × 3 = 2 × dp[9] = 54
7까지는 N // 2 × (N // 2 + N % 2) 통하지만 8부터는 다른 방법으로 접근해야 한다. 그러면 점화식으로 표현 한다면 i, j 반복문으로 1 부터 N까지 돌린다면 아래같은 식이 나온다.
dp[i] = dp[i], j * dp[i - j], j * (i - j) 3개식 중 가장 큰 값으로 저장하면된다. 그러면 시간 복잡도는 O(N ^ 2)이 나온다.
Code
Python
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i // 2 + 1):
dp[i] = max(dp[i], j * dp[i - j], j * (i - j))
return dp[n]
Java
import java.util.Arrays;
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
Arrays.setAll(dp, i -> 0);
dp[1] = 1;
for(int i = 2; i < (n + 1); i++) {
for(int j = 1; j < (i / 2 + 1); j++) {
dp[i] = Math.max(dp[i], j * dp[i - j]);
dp[i] = Math.max(dp[i], j * (i - j));
}
}
return dp[n];
}
}
반복문에서 j 부분에서 i / 2 + 1까지 하는 것은 절반 이상일때 탐색 할필요가 없고 dp도 절반 이하에서 값이 더 큰 값이 나오지 않기 때문이다.
'알고리즘 > Leetcode' 카테고리의 다른 글
[Leetcode] 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers (1) | 2024.03.21 |
---|---|
[Leetcode] 1631. Path With Minimum Effort (0) | 2024.03.15 |
[Leetcode] 131. Palindrome Partitioning (0) | 2024.03.13 |
[Leetcode] 146. LRU Cache (0) | 2024.03.06 |
[Leetcode] 1. Two Sum (0) | 2024.03.05 |
- Total
- Today
- Yesterday
- level2
- 조합
- 문자열
- 넓이 우선 탐색
- Programmerse
- JSCODE
- 재귀호출
- 백준
- Greedy
- spring-boot
- DP
- 수학
- DFS
- 알고리즘
- 백트레킹
- LeetCode
- java
- BaekJoon
- 구현
- 동적 계획법
- 자바
- Python
- 그래프
- 동적계획법
- BFS
- 배열
- 이론
- 그리디
- 파이썬
- 누적합
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |