[TopCoder 알고리즘] 전체탐색 - 암호

Problem : Cryptography

 

TopCoder Security Agency (TSA)는 새로운 암호화 시스템을 개발했다. 이 시스템은 암호화를 위해 숫자 리스트를 입력받는다. 

당신은 TSA의 비밀 정보 수사원이다. 암호화 과정에서 중요한 부분을 구현하는 것이 당신의 임무이다. 당신은 입력 리스트에서 1개의 값을 선택하고 값을 1 증가시킨다. 이때 리스트 내부의 모든 숫자 곱이 가장 커져야 한다.

int[] numbers 형태로 숫자 배열이 주어질 때 곱의 최댓값을 리턴하라. 리턴값이 2^62를 넘는 문제는 나오지 않는다. 

 

 

제약 조건 :

 

capacities : 2-50개의 요소라 있는 배열이며 각 요소의 값은 1-1000이다

리턴값 2^62를 넘지 않는다

 

 

예시 :

numbers = {1 , 2 , 3}

Returns : 12

 

numbers = {1 , 3 , 2 , 1 , 1 , 3}

Returns : 36

 

 

 

---

문제 해설

 

문제의 핵심은 1을 더했을 때 모든 요소의 곱을 값을 가장 크게 만드는 요소를 하나 고르고, 그 결과를 리턴하는 것이다.

 

직관적으로 생각하면 주어진 리스트에서 가장 작은 값, 즉 최솟값을 구한 후 해당 값에 1을 더한 후 전체 요소를 곱해 리턴하면 된다. 해당 요소의 값을 1 증가시켰을 때 전체의 값이 가장 크게 증가하려면 증가시키기 전 해당 값을 제외한 나머지 요소들의 값이 가장 크면 되기 때문이다. 

 

이러한 빠른 해법을 발견했다면

 

① 최솟값을 찾고

② 해당 값을 제외한 나머지 요소의 곱을 리턴 하면 가장 쉽게 문제를 해결할 수 있다.

 

 

하지만 이런 해법을 발견하지 못했더라도,

각 요소를 탐색하며 전체 곱을 구해보고 그중 최댓값을 리턴하는 전체 탐색의 방식을 통해 문제를 해결할 수 있다.

 

---

Python

 

먼저 전체 탐색을 통해 문제의 해결하는 코드는 아래와 같이 짤 수 있다.

 

def Cryptography(numbers):
  result = - float("inf")  
 
  for i in range(len(numbers)) :
    temp_res = 1
    for k, n in enumerate(numbers) :
      if k == i : 
        temp_res *= (n + 1)
      else:
        temp_res *= n
    
    if temp_res > result :
      result = temp_res
 
  return result