[ 프로그래머스 최고의 집합 (Lv3) ] (C++)
프로그래머스의 최고의 집합(Lv3) 문제이다.
[ 문제풀이 ]
문제를 단계별로 나누어서 한번 접근해보자.
#1. 곱이 최대가 되는 경우
우리는 각 원소의 합이 S를 이루면서, 동시에 그 원소들의 곱이 최대가 되는 경우를 구해야 한다.
그럼 과연 어느 경우에 그 곱이 최대가 될까 ??
문제에서 나와있는 설명을 가지고 한번 이야기해보자.
자연수 2개로 이루어진 집합 중 합이 9가 되는 집합을 만들어보자.
[ 1 , 8 ]
[ 2 , 7 ]
[ 3 , 6 ]
[ 4 , 5 ]
이렇게 4개가 존재한다. 그 중에 곱이 가장 큰 경우는 마지막 [ 4 , 5 ] 경우이다.
한가지 예시만 더 들어보자.
자연수 3개로 이루어진 집합 중 합이 7이 되는 집합을 만들어 보자.
[ 1 , 1 , 5 ]
[ 1 , 2 , 4 ]
[ 1 , 3 , 3 ]
[ 2 , 2 , 3 ]
위와 같이 총 4개가 존재한다. 그 중에 곱이 가장 큰 경우는 마지막 [ 2 , 2 , 3 ] 이 된다.
그럼 첫 번째 예시의 결과로 나온 [ 4 , 5 ] 와 두 번째 예시의 결과로 나온 [ 2 , 2 , 3 ] 을 한번 보자.
어떤 공통점이 있을까 ??
뭐 이 2개의 직관적인 공통점을 말하는 것은 아니다. 이 2개의 공통점은, "만들어진 다른 집합들과 비교했을 때, 가장 숫자들 간의 차이가 작다" 라는 것이다.
< 첫 번째 Case >
[ 1 , 8 ] : 원소간의 차이 중 최대차이가 7
[ 2 , 7 ] : 원소간의 차이 중 최대차이가 5
[ 3 , 6 ] : 원소간의 차이 중 최대차이가 3
[ 4 , 5 ] : 원소간의 차이 중 최대차이가 1
< 두 번째 Case >
[ 1 , 1 , 5 ] : 원소간의 차이 중 최대차이가 4
[ 1 , 2 , 4 ] : 원소간의 차이 중 최대차이가 2
[ 1 , 3 , 3 ] : 원소간의 차이 중 최대차이가 2
[ 2 , 2 , 3 ] : 원소간의 차이 중 최대차이가 1
이렇게 주황색으로 칠해진 경우들을 보게 되면, 원소간의 차이가 굉장히 작다는 공통점을 가지고 있다.
그리고 이 경우가 곱이 최대가 되는 경우라는 것을 알 수 있다.
즉 ! "원소간의 차이를 최소화로 만드는 집합이, 원소의 곱이 최대가 되는 집합이 된다."
#2. 집합 만들기
그럼 #1에서 이야기했던, 원소간의 차이가 최소로 이루어진 집합을 어떻게 만들 수 있을까 ??
바로 "나누기와 모듈러 연산을 통해서" 만들 수 있다.
자연수 3개로 이루어진 집합 중 합이 7이 되는 경우를 생각해보자.
먼저, 가장 차이를 작게 만들기 위해서 7을 3개로 한번 나눠보자. 7 / 3 = 2 라는 값을 가지게 된다.
그럼, 일시적으로 먼저 [ 2 , 2 , 2 ] 라는 집합을 만드는 것이다.
하지만, [ 2 , 2 , 2 ] 는 3개의 합으로 7을 만들 수가 없다.
그럼 7을 만들기 위해서는 얼마만큼 더해주어야 할까 ?? '1'만큼을 더 더해주면 된다.
이 '1'은 어디서 나온 걸까 ?? 바로 7 % 3 에서 나온 값이다.
즉, "자연수 3개로 이루어진 집합 중, 합이 7이 되는 집합을 만들기 위해서는 7을 3으로 나눈 수 만큼을 일시적으로 넣어주고,
7 % 3 한 값 만큼 원소들에 더해주면 된다" 는 것이다.
그래서 '1'을 더해줘야 하므로, 하나의 원소에 '1'을 더해주면 [ 2 , 2 , 3 ] 이 된다.
그럼 자연수 3개로 이루어진 집합 중 8이 되는 경우를 생각해보자.
똑같이 8 / 3 = 2 로, [ 2 , 2 , 2 ] 라는 집합을 만들 것이다.
그런데, 추가적으로 더해줘야 하는 값이 8 % 3 = 2 만큼이 더 존재한다.
그럼, [ 2 , 2 , 4 ] 로 만들어주는게 좋을까 ? [ 2 , 3, 3 ] 으로 만들어 주는게 좋을까 ?
아까도 말했듯이, 원소간의 차이를 최소화 시키는 것이 더 큰 결과를 얻을 수 있다.
즉 ! [ 2 , 3 , 3 ] 으로 만들어 주면 된다.
#3. 만들 수 없는 경우
문제에서 만들 수 없는 경우에는 -1을 return 하라고 했는데, 이 경우는 어느 경우일까 ??
바로, n > s 인 경우이다.
자연수 3개로 이루어진 집합 중 합이 2가 되는 집합을 만드세요.
만들 수 있을까 ?? 자연수 3개를 더해서 그 합이 2가 되도록 만들어야 하는 상황이다.
불가능하다.
n > s 인 경우에는 바로 -1 을 return 해버리면 된다.
[ 소스코드 ]
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 | #include <string> #include <vector> using namespace std; vector<int> solution(int n, int s) { vector<int> answer; if (n > s) { answer.push_back(-1); return answer; } int Basic = s / n; int Extra = s % n; answer.assign(n, Basic); // assign(a , b) = vector에 b값을 가지는 원소를 a개 push한다. for (int i = answer.size() - 1; i >= 0 && Extra > 0; i--) { answer[i]++; Extra--; } return answer; } | cs |