TopCoder 전체 탐색! (암호)

문제 

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

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

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

 

 

이번문제는 전체 탐색을 한번 풀어봐서 감이조금 왔다 !! 하지만 결국 책의 도움을 다시 받았다 난 이중 포문을 쓰지 않고 Arrays.short를 사용해서 풀려고 했는데 numbers를 어떻게 해줘야 할지 몰리서 포기했다 .. ㅜ 그래서 책의 도움을 받았다 일단 입력 예시와 리턴 값을 보자

 

[입력예시]

numbers = {1,2,3}

Return 12;

 

음.. 입력예시를 보고 난 더.. 산으로 가버렸다 표를 보고 이해를 하기 시작하고 문제를 풀어 나갓다 표를 보자!

 

+1 하는 요소	계산식	곱
요소 1의경우	2 x 2 x 3	12
요소 2의 경우	1 x 3 x 3	9
요소 3의 경우	1 x 2 x 4	8

표를 보면 감이 잡힐거다 요소가 1일때 배열의 길이 만큼 돌면서 값을 곱해준다 그중에 가장큰 값을 리턴하면된다! 난 처음에 max최대값을 먼저 구해주고 대입되는 숫자가 적으면 초기화 ? 시켜주고 이런식으로 생각하고 문제를 풀어 나갔다 ! 역시나 엉뚱한 생각이였다 말도 안되는 소리를 하는거라고 생각할수도 있다..... 자 넘어가자 자존감이 낮아진다..

 

일단 이중포문을 사용한 풀이다

손으로 풀다 보니 내가 1을 했나? 0이엿나?.. ㅋㅋ 이런 경우가 많아서 이번에는 찍어보고 거기서 나온 숫자랑 내가 풀면서 나온 i 와 j 를 비교했다... ㅜ 멍청한건지 끈기 있는건지 다시한번 느낀다 ..ㅋㅋ ㅋㅋ 결국 손으로 다시 한번 풀어보고 이해를 할수 있었다 문제만 보고 언제 한번 그냥 코딩을 할수 있을지 잘 모르겠다 ..ㅋㅋㅋ

 

 

 

 

처음에는 numbers[0]++; 이 코드를 전혀 생각도 못했다  1을 더해줘야 하는데 어떻게 더해줘야 할지 전혀 감이 안잡혀서 완전 산으로 갔다 

여기서 Arrays.sort를 사용해서 오름차순으로 배열을 정렬해주고 numbers + 1 를 해주고 배열의[i] 만큼 temp와 곱한값을 대입해주면 된다 

 

 

 

 

책의 저자는 이렇게 말했다.

전체탐색으로도 풀수 있지만 수학적인 내용을 가미하면 더 쉽고 효율적인 코드가 된다.

이 문제는 전체탐색으로 풀었지만 수학적인 내용을 알게 된 문제이다.

즉 가장 작은값에 1이 증가하면 곱의 증가율이(n+1)/n이기 때문에 큰 값이 나오게 된다. n이 작으면 작을수록 값이 커지기 때문이다. 전체탐색 소스는 너무 쉽고 제약사항이 없으면 불가능하기 때문에 수학적 내용이 담긴 소스를 기재한다.

그렇다고 한다