[BAEKJOON] 백준 15917: 노솔브 방지문제야!! (C#)

문제 링크

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

 

 

문제

여러분은 Q개의 쿼리를 수행해야 합니다. 수행해야 하는 쿼리는 다음과 같습니다.

어떤 수 a를 2의 거듭제곱 꼴로 나타낼 수 있는가?

 

 

입력

첫 줄에 Q가 주어집니다. (1 ≤ Q ≤ 106)

두 번째 줄부터 Q+1번째 줄까지 a가 주어집니다. a는 1이상 231-1이하 자연수입니다.

 

 

출력

각 쿼리마다, 답이 Yes이면 1을, 그렇지 않으면 0을 출력합니다.

 

 

 

통과한 답안

using System.Text;

namespace _15917
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int Q = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();
            string[] arr = new string[32];
            MakeArr(arr);

            for (int i = 0; i < Q; i++)
            {
                string a = Console.ReadLine();

                if (arr.Contains(a))
                {
                    sb.AppendLine("1");
                }
                else
                {
                    sb.AppendLine("0");
                }
            }

            Console.WriteLine(sb.ToString());
        }

        static string[] MakeArr(string[] arr)
        {
            for (int i = 0; i < arr.Length ; i++)
            {
                arr[i] = Math.Pow(2, i).ToString();
            }

            return arr;
        }
    }
}

 

다양한 방법으로 해결할 수 있는 문제로 힌트에서는 비트로 해결하는 방법을 제시했지만,

힌트를 보지 않고 문제를 풀어서 비트 연산을 적용하지는 못했다.

 

문제를 해결한 방법은 주어진 범위(2의 31제곱)까지의 2의 제곱들을 배열로 저장한 후에

입력되는 값이 해당 배열에 존재하는지 확인하는 방법으로 해결하였다.

이 방법은 주어지는 수를 2의 제곱인지 확인하는 대신,

2의 제곱수들을 가지고 주어진 수와 비교하는 것으로 연산 속도를 빠르게 만들었다.