[BOJ 16974] 레벨 햄버거 (Java)

BOJ 16974 레벨 햄버거

문제풀이

문자열을 실제로 만든다면 너무나도 큰 길이의 문자열이므로 당연히 메모리가 초과된다. 따라서 문자열을 실제로 만드는 것이 아니라 각 레벨에 따른 재료의 개수로 답을 찾는 것을 유추해야한다. 그 이후에는 어떤 경우가 있는지 잘 파악하는 것이 이 문제의 핵심이다.

• 각 레벨에 햄버거는 몇개의 재료를 가질까?
  • 일단 기저 케이스로 레벨 0의 햄버거는 패티만 1개다. 따라서 총 재료의 수는 1이다.
  • 레벨 1부터는 BL(n-1)PL(n-1)B의 형식을 따라가는데 그대로 표현하면 된다.
  • 전체 재료의 개수는 1(번) + h[i - 1](이전 레벨 햄버거의 재료) + 1(패티) + h[i - 1](이전 레벨 햄버거의 재료) + 1(번)
  • 패티의 수는 p[i - 1](이전 레벨 햄버거의 패티) + 1(중간 패티) + p[i - 1](이전 레벨 햄버거의 패티)
• 패티를 몇 개 먹었는지 어떻게 알아낼까?
  • 기저 케이스는 n이 0일때(0레벨 햄버거) x가 0이면(1번째 부터 시작하므로) 0개, x가 1이면 1개(패티만 존재하므로)
  • x가 1일 때는 무조건 첫번째 재료는 번이므로 0
  • x가 중간 패티 위치 보다 작으면 첫번째 번을 빼고 이전 레벨의 햄버거로 재귀
  • x가 중간 패티 위치면 이전 레벨의 패티 수 + 1
  • x가 중간 패티 위치 보다 크면 중간 패티까지의 패티 수 + 이전 레벨의 햄버거 재귀
  • 두 번째 이전 레벨의 햄버거 보다 크면 이전 레벨의 패티 수 * 2 + 1(중간 패티)

구현코드

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

public class Main {
	
	static long[] h, p;
	static int N;
	static long X;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		X = Long.parseLong(st.nextToken());
		
		h = new long[N + 1];
		p = new long[N + 1];
		
		h[0] = 1;
		p[0] = 1;
		
		for(int i = 1 ; i <= N ; ++i) {
			h[i] = 1 + h[i - 1] + 1 + h[i - 1] + 1;
			p[i] = p[i - 1] + 1 + p[i - 1];
		}
		
		System.out.println(solve(N, X));
	}

	private static long solve(int n, long x) {
		
		// n이 감소하여 0이 될 수 있다.
		// 레벨 0 햄버거는 패티 한장이다.
		if (n == 0) {
			if (x == 0) return 0;
			else if (x == 1) return 1;
		}
		
		if(x == 1) {
			// 가장 첫번째 재료는 무조건 번이다.
			return 0;
		} else if(x <= 1 + h[n - 1]) {
			// x가 중간 패티 위치 보다 작으면 첫번째 번을 빼고 이전 레밸의 햄버거를 다시 확인 
			return solve(n - 1, x - 1);
		} else if(x == 1 + h[n - 1] + 1) {
			// x가 중간 패티 위치면 이전 레벨의 패티 수 + 1
			return p[n - 1] + 1;
		} else if(x <= 1 + h[n - 1] + 1 + h[n - 1]) {
			// x가 중간 패티 위치 보다 크면 중간 패티까지의 패티 수 + 이전 레벨의 햄버거 다시 확인
			return p[n - 1] + 1 + solve(n - 1, x - (1 + h[n - 1] + 1));
		} else {
			// 두 번째 이전 레벨의 햄버거 보다 크면
			return p[n - 1] + 1 + p[n - 1];
		}
	}

}