[SWEA]10726. 이진수 표현(java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXRSXf_a9qsDFAXS 

SW Expert Academy

이 문제는 뒤에서 N개까지의 수가 1로 되어 있는지 확인하는 문제이다.

 조건이 1 ≤ N ≤ 30 , 0 ≤ M ≤ 108 이기에

M을 3이라고 한다면 000....011 로 표현된다고 이해하면 된다.

N도 3이라고 한다면 M=3의 뒤에서 N개는 011이고 1이 아닌 자리가 있기 때문에 OFF라고 할 수 있다.

나이브하게 자릿수 단위로 나눠서 홀수인지 짝수인지 풀이해도 되지만, 비트마스킹으로 풀어봤다.

먼저, N을 먼저 binary로 만들어주고 그 수를 binaryN이라 하자. 이 값은 전구가 모두 켜졌을 때의 모범 답안이라고 생각하면 된다.

여기서 이진법으로 바꾼 후 꼭 -1을 해줘야하는데, 이 연산에서 0에서 부터 연산을 시작하고 0을 포함하기에 갯수가 -1을 해줘야 갯수가 N개가 된다.

M과 binaryN을 &연산을 하여 그 값이 binaryN과 같으면 ON, 아니면 OFF를 출력한다.

& 연산을 통해 두 수의 자릿수가 같은지 확인 할 수 있고, 

binaryN과의 비교를 통해 모두 켜져있는지 여부를 확인 할 수 있다.

비트마스킹 방법은 이진법으로 값을 바꿔서 직접 써보면서 하는게 이해에 도움되는 것 같다.

=> N = 4, M = 30이라 한다면

M을 2진수로 표현하면 11110이 된다. 30자리인 2진수로 표현해야하지만 편의상 8자리로 나타내자면 00011110가 된다.

N은 뒤에서 4번째 자리까지 1인 것을 의미하기에 1111이 된다. (10000에서 -1을 해서 만들어줌, 비트마스크에서 1은 true의 의미를 가진다.)

따라서 M & toBinary 는 00011110 & 00001111 이며, 둘을 연산하면 00001110이 된다.

이것은 원래의 toBinary와 비교해서 적절하게 값을 출력해준다.

이 문제는 정답을 만들고, 채점하고, 만점인지 확인하는 흐름인 것 같다.

import java.util.*;
import java.io.*;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        T=Integer.parseInt(br.readLine());
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer st;
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            int toBinary = (1 << N) -1;
            String answer = "ON";
            if( (M & toBinary) != toBinary) answer = "OFF";
            System.out.println("#"+ test_case+ " "+ answer);
        }
    }
}