[백준] 1407번. 2로 몇 번 나누어질까(JAVA)

문제

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

---

풀이(20분)

import java.io.*;
import java.util.*;

public class Main {

    // 5 9면 일단 5 6 7 8 9 인데 앞 뒤 홀수 2개 빠짐, 6과 8로 생각
    // 6 ~ 8 -> 2x ( 1 + 함수(4,4)) 이 4는 나누면서 체크?
    // 25 26 27 28 이면 2개 빼고 26 28임
    // 13 14면 2 x (1 + 함수(14,14)) 이 함수가 2를 반환할거임
    // 176 177 이면 1개 뺴고
    // 함수(176, 176)임
    // 즉 함수는 시작과 끝이 같다면 그걸 2로 나눌 수 있는 만큼 나누고
    // 시작과 끝이 다르면 일단 본인 포함 사이에 있는 홀수 개수 + 함수(제일 첫 짝수, 제일 끝 짝수)의 재귀 구조
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long answer = find(A, B);

        System.out.println(answer);
    }

    static long find(long start, long end){ // 홀수는 빼고, 짝수에 대해서만 추적
        if(start == end){ // 시작과 끝이 같다면
            int count = 0;
            while(true){
                if(end % 2 == 1){ // 2로 나눌 수 있는 만큼 나누어 반환
                    return (long)Math.pow(2, count);
                }
                end /= 2;
                count += 1;
            }
        }

        long oddCounts = 0; // start ~ end 사이에 있는 홀수의 개수
        if(start % 2 == 1){ // 시작이 홀수라면 한칸 미루기
            start += 1;
            oddCounts += 1;
        }

        if(end % 2 == 1){ // 끝이 홀수라면 한칸 땡기기
            end -= 1;
            oddCounts += 1;
        }
        oddCounts += (end - start + 1) / 2; // 사이에 있는 모든 홀수 빼기

		// 홀수 개수 + 2 * find(start/2, end/2)의 재귀
        // start와 end는 짝수이기 때문에 /2로 재귀
        return oddCounts + 2 * find(start / 2, end / 2);
    }
}

---

문제 풀이 전략

 

문제 자체에서 값의 최대 범위가 10^15이다.

→ 절대 일반적인 구조로 해결할 수 없다.

그렇기에 재귀를 생각했다.

 

1. 5 9 입력에 대하여 살펴보자.

• 2로 나눈다는 것은 홀수는 무조건 1의 값을 갖게 된다는 뜻이다.
• 그럼 짝수만 생각하면 된다.
• 6, 8을 구한다고 해보자.
  • 그럼 f(6) = 2, f(8) = 8이다.
  • 2로 나눌 수 있기에, 2로 나눈 3과 4를 기준으로 다시 생각해 보자.
  • f(3) = 1, f(4) = 4이다.
    • 즉 f(6) + f(8) = 2 * (f(3) + f(4))이다.
  • 2로 나눌 수 있는 4를 다시 생각해 보자.
  • 4는 제곱수이기 때문에 별다른 값이 아닌 바로 반환한다.

2. 176 177을 봐보자.

• 176 177 사이에 홀수는 모두 뺄 것이기 때문에 176만 남는다.
• function(176,176)이다.
• 시작과 끝이 같으므로 이 수가 2로 몇 번 나눌 수 있는지만 파악한다.
• 리턴한다.

3. 25 28을 살펴보자.

• 25 28 사이에 홀수를 모두 빼고 시작과 끝을 잡자.
• 25, 27 이 빠지고 시작과 끝은 26, 28로 맞춰진다.
• 2 + 2*find(13,14)가 된다. (2를 곱하는 이유는 2로 나누어 전달할 것이기 때문이다.)
• 13,14의 경우 13이 홀수이기 때문에 시작 : 14, 끝 : 14로 되어 1 + 2 * find(7,7)이 된다.
• find(7,7)은 시작과 끝이 같기 때문에 2로 나눌 수 있는 만큼 나누고 1로 반환된다.