백준 20408번 춘배가 선물하는 특별한 하트 G5 - Hash

 

ㅋㅓ엽다

 

 

문제가 간단하다.

 

문제를 잘 읽으면

N 을 반 쪼개서 1차이로 나누는 로직이 존재합니다이

홀수면 N-1/2 랑 N-1/2 로 나누고, 짝수면 반반 가져가게 되는데

이런 과정을 모두 Set에 담아줍니다. 그리고~ 여기에 M이 포함되면 Yes 해주면 꿑 꿑 꿑

만약 130이 N 이라면

요로코롬.. 주루루 저장이 된다.

규칙이 존재하는데 홀수가 나타나는 순간 두 갈래로 갈라진다.

짝수라면 반반 이고 중복 저장 안하니까 1개씩 저장된다.

 

코드로 보잡

 

import java.io.*;
import java.util.*;
 
public class Main { //Boj_30408_춘배가 선물하는 특별한 하트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        long N = Long.parseLong(st.nextToken());
        long M = Long.parseLong(st.nextToken());
 
        Set<Long> set = new HashSet<>();
        set.add(N);
 
        boolean flag = (N % 2 == 0) ? false : true; // 홀수 판단
        while (N > 1) {
            if (flag) { // 홀수가 나온 경우
                N /= 2;
                Long temp = N;
                set.add(temp);
                set.add(temp + 1);
            }else{ // 한번도 홀수가 안나오는 경우
                if (N % 2 == 0) {
                    N /= 2;
                    Long temp = N;
                    set.add(temp);
                } else if (N % 2 == 1) {
                    flag = true;
                    N = (N-1)/ 2;
                    Long temp = N;
                    set.add(temp);
                    set.add(temp + 1);
                }
            }
        }
 
        if(set.contains(M)){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
 
}