문제 내용
상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.
- 레벨-0 버거는 패티만으로 이루어져 있다.
- 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)
예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티)
상도가 상근날드에 방문해서 레벨-N 버거를 시켰다. 상도가 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까? 한 장은 햄버거번 또는 패티 한 장이다.
원본 문제 바로가기
입력
첫째 줄에 N과 X가 주어진다.
출력
첫째 줄에 상도가 먹은 패티의 수를 출력한다.
제한
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 755 | 344 | 266 | 51.451% |
- 1 ≤ N ≤ 50
- 1 ≤ X ≤ 레벨-N 버거에 있는 레이어의 수
문제 풀이 아이디어
먼저, 문제 상황을 이해해봅시다.
아래의 그림과 같이 주어진 문제에서 햄버거를 구성하는 방식을 도식화하였습니다.
여기서, 는 레벨 i에서의 햄버거를 말합니다.
햄버거는 패티 또는 번의 집합체입니다.
첫번째 아이디어입니다.
L-레벨 햄버거를 String 객체 또는 StringBuilder/Buffer 객체로 구현한 후
X만큼 선형적으로 탐색하면?
하지만 저의 개발 환경에서는 L=29일 때부터,
java.lang.OutOfMemoryError:Java heap space가 발생했습니다.
이건 왜 그럴까요?
그 이유로, String 객체의 최대 길이는 힙 메모리의 크기에 의해 결정되기 때문에,
현재 주어진 문제에서 최악의 경우 L=50일 때의 문자열의 길이는 적어도,
아래의 수식만큼의 길이를 가져야 합니다.
따라서 다른 아이디어가 필요합니다.
꼭 햄버거를 전부 문자열로 구현해야할까?
꼭 햄버거를 전부 구현할 필요는 없었습니다. 그 이유로, 현재 문제에서는 L레벨 햄버거를 X개만큼 먹을 때, '패티가 얼마나 있는가?'가 핵심입니다.
i 레벨의 햄버거가 있을 때, 아래부터 X장을 먹는 과정을 일반화하면 아래와 같을 것 입니다.
여기서 우리는 i-1 레벨의 햄버거의 길이가 X와 크거나 작은지, 같은지를 비교하고,
1. 만약 같다면 해당 i-1레벨에서 패티가 얼마나 있는지 확인하고
2. 만약 작다면 해당 중간 패티를 넘어서 또 다른 i-1레벨의 햄버거를 먹고,
3. 만약 크다면 i-1레벨 햄버거안의 i-2레벨 햄버거를 조사한 다음 얼마나 패티를 먹는지 조사합니다.
구현
- L레벨에서의 햄버거의 길이, 패티의 갯수를 담은 배열을 각각 만들어 둡니다.
public static final int LAYER = 50;
public static long[] burger = new long[LAYER + 1]; // 각 Layer의 먹을 수 있는 패티 또는 번의 개수
public static long[] patties = new long[LAYER + 1];
public static long count = 0;
- 햄버거의 길이, 패티의 개수 배열을 초기화합니다.
여기서 패티는 한 레벨마다 이전 레벨 패티의 두 배와 1개의 중간 패티가 추가된다는 점,
햄버거의 길이는 이전 레벨 햄버거 길이의 두 배와, 2개의 번, 1개의 패티가 추가된다는 점을 이용해 구할 수 있습니다.
patties[0] = 1;
burger[0] = 1;
/* 각 Layer의 번 개수, 패티 개수 계산 */
for (int i = 1; i <= 50; i++) {
patties[i] = 2 * patties[i - 1] + 1;
burger[i] = 2 * burger[i - 1] + 3;
}- 재귀함수를 구성합니다.
base cases는 (a)와 (b) 같이 생각할 수 있습니다.
(a) 더 이상 먹을 패티 또는 번이 없는 경우, 다시 말해 X==0인 경우
(b) 최초 L=0 레벨 햄버거까지 도달한 경우
전체 소스코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static final int LAYER = 50;
public static long[] burger = new long[LAYER + 1]; // 각 Layer의 먹을 수 있는 패티 또는 번의 개수
public static long[] patties = new long[LAYER + 1];
public static long count = 0;
public static void burger(int N, long X) {
/* base case 1 : 더 이상 먹을 패티 또는 번이 없는 경우 */
if (X == 0) {
System.out.println(count);
return;
}
/* base case 2 : 햄버거 Layer-0 까지 온 경우 */
else if (N == 0) {
count++;
System.out.println(count);
return;
}
X--; // (N-1)-layer의 버거에 들어가기전 N-버거의 맨 밑의 번 먹음
/* 레이어 N에 존재하는 햄버거의 크기와 내가 먹어야하 는 X의 개수가 같냐? 작냐? 크냐에 따라*/
if (X == burger[N - 1]) { // 내가 먹어야 하는 버거 또는 패티가, N-1 층의 버거 수와 같음.
count += patties[N - 1];
X -= burger[N - 1];
burger(N - 1, X);
} else if (X > burger[N - 1]) { //내 가 먹어야 하는 버거 또는 패티가, N-1층의 버거 수보다 큼.
count += patties[N - 1] + 1; // 중간 P 먹고 위에 N-1층도 먹어야겠네.
X -= (burger[N - 1] + 1); // 중간 P 먹은거 포함
burger(N - 1, X);
} else { // 내가 먹어야하는 버거 또는 패티가 N-1층의 버거 수 보다 작음
burger(N - 1, X); // 더 깊이 탐색할 필요가 있음
}
}
/**
* 주어진 로직대로 시뮬레이션 했을때, 먹은 패티 수 반환하기
*
* @param N
* @param X
*/
public static void solution(int N, long X) {
patties[0] = 1;
burger[0] = 1;
/* 각 Layer의 번 개수, 패티 개수 계산 */
for (int i = 1; i <= 50; i++) {
patties[i] = 2 * patties[i - 1] + 1;
burger[i] = 2 * burger[i - 1] + 3;
}
burger(N, X);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
long X = Long.parseLong(st.nextToken());
solution(N, X);
}
}