C++ 과외내용 정리 - 1주차 문제풀이 (1074 - Z)

문제풀이는 거두절미하고 시작합니다?

0. 거두절미 해도 헛소리는 빼놓을 수 없어. ( 다람쥐 사육사 )

다람쥐 사육사 {3}{B}{G}
생물 — 엘프 드루이드
다람쥐 사육사가 전장에 들어올 때, 1/1 녹색 다람쥐 생물 토큰 두 개를 만든다.
{3}{B}, {T}: 당신이 조종하는 다람쥐들은 턴종료까지 +1/+0을 받고 호전적을 얻는다.
2/2

그치만 재미있다고요. 다람쥐 사육사는 매직 더 개더링에 나오는 카드 중 하나입니다. 최근 위와 같은 카드를 나무위키 템플릿에 맞춰 만들어주는 간단한 프로그램을 작성해서 이야기해보고 싶었어요. 왜 저 카드냐고요? 테스트용으로 쓰이고 있거든요.

1. 문제 소개 - Z

한 변이 2^N인 정사각형 모양의 배열을 Z자로 탐색합니다. 재귀적으로요!

(이해가 안 가시면 문제에 들어있는 사진을 참고해 주세요)

그럼 r행 c열은 몇 번째로 방문하게 될까요?

 

설명을 쓰기 전에 풀고 와야겠죠? 잠시만요!

시작 - 2022.06.14.08.23.

끝 - 2022.06.14.09.00.

 

2. 풀이

long long	pow2(int n){
	static long long	m[31] = {1, }; // 메모이제이션을 위한 배열, 2^0 = 1

	if(!m[n]){
		m[n] = pow2(n - 1) * 2;
	}
	return m[n];
}

최적화를 위해 math헤더를 안 썼습니다. pow함수가 있을 거 같긴 했는데 풀고 나서 찾아봤습니다. 그래도 이게 더 빨라요! 한 번 계산해둔 값은 다시 계산하지 않거든요! m이 31인 이유는 이 문제에서 N이 최대 15인데, 2N 이상(사실 코드 짜고 보니 2N-2였어요)의 값은 필요없기 때문입니다.

 

long long F(int N, int c, int r){
	if(N == 0) return 0;
    
	// 대충 side 계산은 생략한다
	
	return F(N - 1, c, r) + pow2(2 * N - 2) * side;
}

문제 풀이의 핵심이 되는 함수입니다. 전부 옮겨오긴 좀 그래서 일부 생략했어요.

각 사분면이 Z모양으로 나뉘는 걸 반복하기 때문에, 그 나뉘는 부분의 시작값과 나눈 부분에서의 값을 더해주는 그런 식으로 풀었습니다. 수학적 귀납법을 이용한 풀이에요. 근데 이거 수학적 귀납법으로 설명을 못하겠습니다.