[Java] 8993. 하지 추측

D4-8993. 하지 추측

 

문제출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW6GFM8aLacDFAVX&categoryId=AW6GFM8aLacDFAVX&categoryType=CODE

SW Expert Academy

 

N = 2k - 1(홀), N = 2k(짝) 두개의 경우로 나누어 생각해보았다. k가 순수 2의 거듭제곱 수 일때만 종료.

프로그램이 종료하기 위해서는 N 이 2의 거듭제곱이어야 함을 이해하면 쉽게 해결할 수 있다.

 

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;

class Solution {
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++)	{
			long N = sc.nextLong();
			if (N % 2 != 0)
				bw.write("#" + test_case + " NO\n");
			else {
				while (N % 2 == 0) {
					N = N >> 1;
				}
				if (N == 1)
					bw.write("#" + test_case + " YES\n");
				else
					bw.write("#" + test_case + " NO\n");
			}
		}
		
		bw.flush();
		bw.close();
	}
}