백준 12931 자바 - 두 배 더하기 (BOJ 12931 JAVA)

https://www.acmicpc.net/problem/12931

 

  우선 처음으로 생각할 부분이, 만약 시작지점인 0,0,0,... 에서 시작해서 제시된 B 배열을 찾아가려면 결국 모든 경우를 봐야한다. 매번 B 배열과 비교하며 최소 연산 횟수를 찾게 짜는건 사실상 무리라고 본다. 그럼 반대로 B 배열에서 0,0,0,...을 찾아가는걸 생각해보자.

 

  제시된 연산은 각각에대해 1을 더하는 것과 전체에 대해 2를 곱하는 것이므로, 반대로 B배열에서 0,0,0,... 을 찾아가기 위해서는 각 배열에 대해 1을 빼는 연산과, 전체에 대해 2로 나누는 과정을 거쳐야 한다. 그럼 N=1일 때 조차도 무조건 2로 나누는 것이 이득인 것을 쉽게 알 수 있다. (더 적은 연산으로 차이를 더 많이 낼 수 있음)

 

  최종적으로 이 문제는 간단하게 B -> 0,0,0,... 을 만들면서 모두를 2로 나눌 수 있다면(전부 짝수거나 0이라면) 무조건 2로 나누고, 그게 아니라면 모두를 짝수 혹은 0으로 만드는 과정을 반복하면 된다. 즉 그리디 알고리즘 방식을 택하면 쉽게 풀 수 있다.

 

  코드에서도 마찬가지로 모두 0이 되기 전까지(!isEnd()) 모두 짝수로 만드는 과정(makeAllEven())과 2로 나누는 과정(makeHalf())를 반복하며, 이 때의 횟수가 결국 최소 연산 횟수이다.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/12900/BOJ_12931.java