23.02.24 파이썬 코딩 퀴즈#172 최고의 집합(프로그래머스 스쿨)

이번 문제는 최고의 집합이다.

자연수 n 개로 이루어진 중복집합중에 각 원소의 합이S가 되고, 각 원소의 곱이 최대가 되는 집합을 최고의 집합이라고 한다.

위 예시처럼 S 가 9 이고 N이 2 가 주어졌을때, 4개의 집합이 나올 수 있고, 이중 최대곱은 {4,5} 이므로 이를 배열 [] 로 만들어서 반환하면 된다. 만약 존재하지 않는다면 [-1]을 반환하면 된다.

여기서 한가지 힌트를 얻을 수 있는데, 인접한 두 수를 곱한 값이 최대라는 점이다.

 

만약 n 이 3이라면 어떻게 될까?

S는 동일하게 9 라고 가정하면, 첫번째 원소가 1인 경우에는 {1,1,7}, {1,2,6},{1,3,5},{1,4,4} 가 나온다.

첫번째 원소가 2라면 {2,2,5}, {2,3,4} 2개가 나온다. ({2,1,6}은 중복이기에 포함하지 않는다)

첫번째 원소가 3이라면 {3,3,3} 한개만 존재한다.

첫번째 원소가 4가 되면 이는 위에 나온 항들의 중복이기에 포함되지 않는다.

여기서 최대값은 3x3x3 = 27이다. 즉 같은 원소들로 이루어진 중복 집합의 곱이 최대이다.

 

즉, 인접한 연속수를 이용하여 만들 수 있는 집합 또는 동일한 수로 만들수 있는 중복 집합을 찾아야 한다.

코드는 굉장히 단순하고 간단하다.

먼저 s가 n 으로 나누어 떨어지는 경우라면 동일한 수로 이루어진 중복 집합을 찾아야 한다.

그리고 그 수는 s//n 이며 이 수가 n 개 만큼 존재하는 answer 집합을 만들어 주면 된다.

나누어 떨어지지 않는 경우라면 s를 n 으로 나눈 몫만 사용하여 answer에 전달하면 된다.

이때 한번 몫을 구한 만큼 s에서 감소시켜 주고, 구해야 할 n개에서 1개 빼주면 된다.