문제

BOJ 16974: 레벨 햄버거 https://www.acmicpc.net/problem/16974

풀이

조건

• 레벨-0 버거는 패티만으로 이루어져 있다.
• 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)

풀이 순서

• 각 레벨에 따른 재료의 갯수로 답을 찾아야 한다.
• 각 레벨에서 햄버거의 총 재료 수를 구한다.
  • 레벨 0에서는 패티만 1개 이므로 총 재료 수는 1이다.
  • total[] 배열을 사용해 레벨 별로 총 재료 수를 구해 넣어준다.
  • 문제에서 알려준 대로 넣으면 된다.
    • 1(빵) + total[i - 1](이전 레벨 햄버거의 재료) + 1(패티) + total[i - 1](이전 레벨 햄버거의 재료) + 1(빵)
• 각 레벨에서 햄버거의 총 패티 수를 구한다.
  • 위에서 총 재료 수를 구한 방법처럼 pat[] 배열에 레벨 별로 패티 수를 구해 넣어준다.
  • pat[i - 1](이전 레벨 햄버거의 패티) + 1(중간 패티) + pat[i - 1](이전 레벨 햄버거의 패티)
• 패티를 몇 개 먹었는지 구한다.
  • 아래 코드에 적어놓은 주석을 보면 이해가 쉽다.
  • n이 0일때(0레벨 햄버거) x가 0이면(하나도 먹지 않은 경우) 0개, x가 1이면 1개(패티만 1장 있는 상태)
  • x가 1일 때는 1번째만 먹으면 빵만 있으므로 0
  • x가 중간 패티 위치 보다 작으면 맨 앞의 빵을 빼고 이전 레벨의 패티 수를 호출
    • 맨 앞의 빵을 빼기 위해 x-1을 넣어 줌
  • x가 중간 패티 위치에 있다면 이전 패티의 수 + 1(중간 패티를 포함해야 함)
  • x가 중간 패티 위치보다 크면 중간 패티까지의 패티 수 + 이전 레벨의 햄버거 재귀
  • x가 현재 햄버거의 총 재료 수와 같다면 현재 레벨에서의 패티 수를 반환
    • 이전 패티 수 * 2 + 중간 패티 1

코드

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

public class Main {
    
	static int N;
	static long X;
	static long[] total, pat;
	static int cnt = 0;
	
    public static void main(String[] args) throws IOException {
    	Scanner sc = new Scanner(System.in);
    	
    	N = sc.nextInt();
    	X = sc.nextLong();
    	
    	sc.close();
    	
    	total = new long[N+1]; // 총 재료 수
    	pat = new long[N+1]; // 패티 수
    	total[0] = 1;
    	pat[0] = 1; // 0 레벨에선 패티만 1개 있다
    	
    	// N 레벨까지 총 재료 수와 패티 수를 구한다
    	for(int i=1; i<=N; i++) {
    		total[i] = 1 + total[i-1] + 1 + total[i-1] + 1;
    		pat[i] = pat[i-1] + 1 + pat[i-1];
    	}
    	
    	// 재귀 호출 시작
    	long ans = recursion(N, X);
    	
    	System.out.println(ans);
    }

    static long recursion(int n, long x) {
    	// 재귀 호출로 n이 0이 되면 패티만 1장인 상태이다.
    	if(n == 0) {
    		// 하나도 안 먹음
    		if(x == 0) {
    			return 0;
    		} 
    		// 한 장 먹음
    		else if(x == 1) {
    			return 1;
    		}
    	}
    	
    	// 햄버거가 1장이 아닌 상태에서 1번째만 먹으면 패티를 먹을 수 없다 -> 빵만 있음
    	if(x == 1) {
    		return 0;
    	} 
    	// x가 중간 패티 위치보다 작으면 맨 앞의 빵을 빼고 이전 레벨의 패티 수를 호출
    	// 맨 앞의 빵을 빼기 위해 x-1을 넣어 줌
    	else if(x <= 1 + total[n-1]) {
    		return recursion(n-1, x-1);
    	} 
    	// x가 중간 패티 위치에 있다면 이전 패티의 수 + 1(중간 패티를 포함해야 함)
    	else if(x == 1 + total[n-1] + 1) {
    		return pat[n-1] + 1;
    	} 
    	// x가 중간 패티 위치보다 크면
    	else if(x <= 1 + total[n-1] + 1 + total[n-1]) {
    		return pat[n-1] + 1 + recursion(n-1, x - (1 + total[n-1] + 1));
    	} 
    	// x가 현재 햄버거의 총 재료 수와 같다면 현재 레벨에서의 패티 수를 반환
    	// 이전 패티 수 * 2 + 중간 패티 1
    	else {
    		return pat[n-1] + 1 + pat[n-1];
    	}
    }
	
}

정리

• 처음에 String 값에 재귀를 통해 햄버거의 모양을 구한 뒤 답을 찾으려 했는데 시간초과와 메모리 초과가 나서 실패했다.
  • 문제 조건을 제대로 보자.
• 수학적인 해결 방법을 찾는 연습을 해야겠다.