처음에 문제를 보자마자 생각이 들었던 접근법은 DP나 그리디였다. 하지만 뾰족한 수가 떠오르지 않아서 다른 방법을 찾던 도중 간단한 아이디어가 떠올라서 테스트만 해보려고 했는데 정답을 받아버렸다. 어떤 한정된 수가 있고 그 수를 잘 나눠서 곱이 최대가 되기 위해서는 각 숫자들이 비슷해야 한다. 수학적인 워딩으로 다시 말하면 각 수의 편차가 적어야 한다. 이런 내용에 대한 포멀한 증명을 해본 적은 없지만 살다보니 경험적으로 깨우친 것 같다.
집합의 각 원소는 정수이므로 우선은 s를 n으로 나눴을 때의 몫을 구한다. 그리고 나머지는 원소에 적당히 1씩 배분하는 식으로 문제를 해결했다. vector를 사용했기 때문에 상당히 쉽게 구현할 수 있었다.
'PS > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 단어 변환 (0) | 2022.10.02 |
|---|---|
| [프로그래머스] 야근 지수 (2) | 2022.10.01 |
| [프로그래머스] 섬 연결하기 (2) | 2022.01.06 |
| [프로그래머스] 정수 삼각형 (9) | 2022.01.04 |
| [프로그래머스] 등굣길 (0) | 2022.01.02 |