[수학] 백준 - 레벨햄버거

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

16974번: 레벨 햄버거

 

-문제해설

자바에서 처음에 문자열을 구해서 풀다가 String 최대값을 벗어나서 메모리 초과가 계속 떳다...

다른 사람 풀이 참고했더니 재귀함수와 수학을 이용해서 푸는 문제였다.

 

방법은 맨 처음에 각 레벨의 전체재료수와 각 레벨의 패티수를 배열에 저장해준다.

레벨1의 전체 재료수는 빵1 + 패티3 + 빵1 = 5이고, 패티수는 3이다.

레벨2의 전체 재료수는 빵1 + (빵1 + 패티3 + 빵1) + 패티1 + (빵1 + 패티3 + 빵1) + 빵1 = 13이고, 패티수는 7이다.

 

이를 수식화하면 다음과 같다.

h[n] = 레벨 n의 전체 재료수 = 1 + (레벨 n-1의 전체재료수) + 1 + (레벨 n-1의 전체재료수) + 1

p[n] = 레벨 n의 패티수 = (레벨 n-1의 패티수) + 1 + (레벨 n-1의 패티수)

이때 h[0]과 p[0]은 1로 선언해놓는다.

 

다음으로는 x값에 대해 각 레벨에 대한 범위를 나누는 것이다.

예를 들어 레벨2 햄버거이고 x값이 7이라면 범위는 아래와 같다.

 

BBPPPB / P / BPPPB / B

총 4개의 구간이 생긴다.

첫 번째는 x값이 중간패티 위치보다 작은 경우

두 번째는 x값이 중간패티 위치와 같은 경우

세 번째는 x값이 중간패티 위치보다 크고 전체 재료수보다 작은 경우

네 번째는 x값이 전체 재료수와 같은 경우

 

x는 7이었으니깐 두 번째 경우에 해당한다. 이 경우 레벨1의 패티수에서 중간패티 1을 더해주면 정답이 된다.

레벨1의 패티수는 p[1] =3 이고 중간패티 1을 더하면 정답 4가 된다.

 

만약에 x가 6이라면

첫 번째 경우에 해당되고 재귀함수를 이용해서 레벨1 햄버거의 패티수를 계산한다.

재귀함수는 다음과 같다.

getPetty( 레벨, x값 )

 

여기서 이전 레벨로 내려갈 때 x값은 -1 해줘야 한다. 왜냐하면 레벨2에서는 BBPPPB ~ 인데 레벨1에서는 BPPPB이므로

앞에 B의 길이를 빼준다. 

이렇게 x=5가 되어서 레벨1 햄버거로 내려오면 레벨1 햄버거의 네 번째 범위에 해당되므로 레벨1의 패티수인 p[1]값을 반환시켜준다.

 

그러면 답은 3이된다.

 

이번에는 만약에 x가 8이라면 세 번째 범위에 해당된다.

일단 중간패티수까지의 패티수를 계산해준다. p[1]+1

그리고 여기에다가 레벨 1 햄버거의 추가적인 패티를 계산해준다.

이때 추가적인 패티를 계산하기 위해 x값에서 레벨 2 햄버거의 중간패티길이까지 빼준다.

x - (1 + h[1] + 1) = 8 - 7 = 1

재귀함수는 getPetty( 레벨1, 1 );

 

그러면 레벨1에서 첫 번째 범위에 해당된다. 

나머지는 소스코드를 보면서 이해해보자.

 

 

 

-자바

package math;

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

public class BJ16974 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int N;
	private static long X;
	private static long[] h, p;
	private static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer( br.readLine() );
		N = Integer.parseInt( st.nextToken() );
		X = Long.parseLong( st.nextToken() );

		//h는 레벨의 전체햄버거 재료수, p는 레벨의 패티수
		h = new long[N+1];
		p = new long[N+1];
		h[0] = p[0] = 1;
		
		//n레벨까지 전채 재료수와 패티수를 구한다.
		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];
		}
		
		//패티수 반환해주는 메소드 호출
		bw.write( getP( N, X ) +  "\n" );
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static long getP( int n, long x ) {
		//재귀호출로 인해 n이 0이 될경우 레밸 0의 패티는 한 장이다. bpb
		if( n==0 ) {
			if( x==0 ) return 0;
			else if( x==1 ) return 1;
		}
		
		//각 레벨의 첫 번째 자료는 패티가 아니므로 0반환
		if( x == 1 ) return 0;
		
		//x가 중간패티 위치보다 작으면 맨 앞에 번을 빼고 이전 레밸의 햄버거 패티수를 호출
		//맨 앞에 번을 빼기 위해 x-1을 해준다.
		else if( x <= 1+h[n-1] ) return getP( n-1, x-1 );
		
		//x가 중간패티의 위치라면 이전 패티수+1을 반환
		else if( x == 1+h[n-1]+1 ) return p[n-1]+1;
		
		//x가 중간패티 위치보다 크면 
		else if( x <= 1+h[n-1]+1+h[n-1] ) return p[n-1]+1+getP( n-1, x-(1+h[n-1]+1) );
		
		//x가 현재 레밸 재료수의 크기와 같다면 현재 레밸의 패티수를 반환
		else return p[n-1]+1+p[n-1];
	}

}

 

-파이썬

def getP( n, x ):
    if n==0:
        if x==0: return 0
        elif x==1: return 1  
    elif x==1:
        return 0
    elif x <= 1+h[n-1]:
        return getP( n-1, x-1 )
    elif x == 1+h[n-1]+1:
        return p[n-1]+1
    elif x <= 1+h[n-1]+1+h[n-1]:
        return p[n-1]+1+getP( n-1, x-(1+h[n-1]+1) )
    else:
        return p[n-1] + 1 + p[n-1]

n, x = map(int, input().split())
h = [1] * (n+1)
p = [1] * (n+1)

for i in range( 1, n+1 ):
    h[i] = 1 + h[i-1] + 1 + h[i-1] + 1
    p[i] = p[i-1] + 1 + p[i-1]
    
print( getP( n, x ) )