백준 24927 자바 - Is It Even? (boj 24927 java)

문제 : boj24927

 

※ 2K로 나누어 떨어지는지 구하면 안되고, 2^K(2의 K승)로 나누어 떨어지는지 구해야 한다. 문제에 오류가 있다.

 

  이걸 직접 계산해서 실제로 나누어 보려고 한다면 무려 90만1자리의 엄청난 수가 나온다 ㅋㅋ. 그러니 생각을 좀 바꿔보자. 어차피 2^K으로 나누어 떨어지는지만 확인하면 되므로, 단순히 2^K 성분만 확인하면 된다. 다른 소수는 생각할 것도 없다! 무슨말이냐면, 소인수 분해를 생각해보자.

  위와 같이 어떠한 수를 소인수분해 했을 때 2가 몇개 있는지만 알면 된다. 240의 경우 2가 4개 존재한다. 3이랑 5는 상관이 없다. 2가 4개인 수를 나눌 수 있는 2^K는 K개 4이하일 때 가능하다.

 

  즉, 주어진 x_i을 2로 나누어지지 않을 때 까지 계속 나누면서 2로 몇 번 나누어지는지 확인한다. 그걸 cnt라고 할 때, K가 cnt보다 작거나 같다면 1을 출력하고 아니면 0을 출력하면 된다.

 

  2로 더이상 나누어 떨어지지 않을 때 까지 2로 나누면서 수를 세는건 다음과 같이 가능하다. (cur이 x_i 해당함)

int cur = Integer.parseInt(br.readLine());
while (cur%2==0) {
    cnt++;
    cur/=2;
}

 

  다른 방법으로는 다음과 같이 해도 된다. i를 높은 수 부터 내려오면서, 2^i로 나누어 떨어진다면 cnt에 i를 더하는 방식이다.

int cur = Integer.parseInt(br.readLine());
for (int i = 29; i > 0; i--) {
    if (cur%(1<<i)==0) {
        cnt += i;
        break;
    }
}

 

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int cnt = 0;
        while (n-->0) {
            int cur = Integer.parseInt(br.readLine());
            while (cur%2==0) {
                cnt++;
                cur/=2;
            }
        }
        System.out.println(cnt>=k?1:0);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}