[TopCoder] Cryptography (C#, Java)

---

TopCoder Security Agency는 새로운 암호화 시스템을 개발했습니다. 이 시스템은 암호화하려고 숫자 리스트를 입력받습니다.

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

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

---

 

문제 파악하기

1. 기본적으로 모든 숫자의 곱인데, 하나의 숫자만 1이 커야한다.
모든 숫자의 곱보다는 큰 값이어야 하므로, 기본 max값을 모든 숫자의 곱으로 설정한다.

2. 숫자 하나씩 1을 더해가며 max값과 비교한다.

3. 2^62를 넘는 값이 없다는 것은 2^62까지 고려해야 한다는 말
즉, int(32bits)가 아닌 long(64bits)을 사용해야 한다.

 

전체 코드

(C#)

        private static long Solution(int[] numbers)
        {
            long mul = 1;
            foreach (int n in numbers) mul *= n;
            long max = mul;

            for (int i = 0; i<numbers.Length; i++)
            {
                if (mul / numbers[i] * (numbers[i] + 1) > max) max = mul / numbers[i] * (numbers[i] + 1);
            }

            return max;
        }

 

(Java)

public class Cryptography{
    public long encrypt(int[] numbers){
        
        long mul = 1;
        
        for (int i=0; i<numbers.length; i++){
        	mul *= (long)numbers[i];
        }
        
        long answer = mul;
        for (int i=0; i<numbers.length; i++){
        	if((long)mul/numbers[i]*(numbers[i]+1) > answer) answer = (long)mul/numbers[i]*(numbers[i]+1);
        }
        
    	return answer;
    }
}