[알고리즘 문제 풀기] 두 배 더하기(12931)

1. 문제 풀이 아이디어

• 2로 나누는 최대 횟수를 구하고, 1을 빼는 횟수를 누적하여 최소 연산 횟수를 계산하여 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int maxDiv = 0;
    int count = 0;
    string[] split = sr.ReadLine().Split();
    for (int i = 0; i < n; i++)
    {
        int b = int.Parse(split[i]);
        int div = 0;
        while (b > 0)
        {
            if (b % 2 == 0)
            {
                b /= 2;
                div++;
            }
            else
            {
                b--;
                count++;
            }
        }
        maxDiv = Math.Max(maxDiv, div);
    }
    sw.WriteLine(maxDiv+count);
}

3. 정리

• 각 숫자에 대해 2로 나눌 수 있는 최대 횟수를 div에 저장하고, 1을 뺀 횟수를 count에 누적한다.

• maxDiv를 갱신하여 가장 많이 나눈 횟수를 찾는다.

• maxDiv + count를 출력하여 최소 연산 횟수를 계산하여 문제를 해결한다.