Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 바질토마토뭐시기
- javascript
- 나쫌
- 발더스게이트
- 발더스3
- 토이프로젝트
- 버즈2프로
- 코테
- 메탈퍼즐
- DIY
- LeetCode
- 알고리즘테스트
- 취미
- 누룽지소금빵
- 코딩테스트
- 메일우유
- 맛집
- 송리단
- 노노그램
- 서울제빵소
- 눈알빠지겠네
- 발더스모드
- 하스스톤
- 천등
- 밥먹고
- 미앤아이
- 뜨아거
- 3d퍼즐
- 게임
- 잠실새내
Archives
- Today
- Total
.Zzumbong
[leetCode/JS] 343. Integer Break 본문
난이도 [ 🤔 ] Medium
문제 설명
Given an integer n
, break it into the sum of k
positive integers, where k >= 2
, and maximize the product of those integers.
Return the maximum product you can get.
입출력 예
Example 1:
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Constraints
2 <= n <= 58
내 솔루션
- 1 부터 12까지 손으로 계산해보고 규칙이 있는지 확인해봤다.
// 여긴 예외
// 2: 1 1 = 1
// 3: 2 1 = 2
// 그냥 3이 많으면된다.
// 4: 2 2 = 4
// 5: 3 2
// 6: 3 3
// 7: 3 2 2
// 8: 3 3 2
// 9: 3 3 3
// 10: 3 3 2 2
// 11: 3 3 3 2
// 12: 3 3 3 3
- 결론은 3이 많으면 된다.
- 2, 3은 예외처리로 n - 1 한다.
- 4 ~ n 은 4보다 크면 3으로 빼고, 4이하는 그대로 사용한다. ( result * 4 === result * 2 * 2 이므로 )
- 그래서 아래와 같이 코드가 나왔다.
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
if(n === 2 || n === 3) return n - 1;
let result = 1;
while(n > 4){
result *= 3
n -= 3
}
return result * n
};
감상평
- 이런게 진짜 재미있는 문제 아닐까?
- leetCode 특유의 이해하기 쉬운 간결한 문제와 짧고 맛있는 풀이 과정
- 이걸 DP나 DFS로 푼 사람들도 있던데.. 진짜 들은 다른 세상에 사는 거 같다.
'coding test > leetCode' 카테고리의 다른 글
[leetCode/JS] 706. Design HashMap (0) | 2023.10.04 |
---|---|
[leetCode/JS] 6. Zigzag Conversion (0) | 2023.10.04 |
[leetCode/JS] 1512. Number of Good Pairs (0) | 2023.10.03 |
[leetCode/JS] 2038. Remove Colored Pieces if Both Neighbors are the Same Color (0) | 2023.10.02 |
[leetCode/JS] 557. Reverse Words in a String III (0) | 2023.10.01 |
Comments