Jumping

Jumping.cpp

// Exam1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include "pch.h"
#include <iostream>
#include <vector>

using namespace std;

struct Step
{
public:
	Step() : currentStep(0), stepPower(1) {}
	int currentStep;
	int stepPower;
};

int maxStep(int n, int k)
{
	if (n <= 0)
		return 0;

	int maxNumber = 0;
	vector<Step> allSteps((1 << (n + 1)) - 1, Step());
	for (int i = 1; i <= n; i++)
	{
		for (int j = (1 << i) - 1; j < (1 << (i + 1)) - 1; j++)
		{
			bool isRight = (j % 2 == 0);
			int parent = (j - ((1 << i) - 1)) / 2 + ((1 << (i - 1)) - 1);

			Step newStep = allSteps[parent];
			if (newStep.stepPower == 0)
			{
				allSteps[j] = newStep;
				continue;
			}

			if (isRight)
			{
				newStep.stepPower += 1;
			}
			else
			{
				newStep.currentStep += newStep.stepPower;
				newStep.stepPower = 1;
			}

			if (newStep.currentStep == k)
			{
				newStep.currentStep = -1;
				newStep.stepPower = 0;
			}
			
			allSteps[j] = newStep;

			if (maxNumber < newStep.currentStep)
				maxNumber = newStep.currentStep;

		}
		cout << endl;
	}

	return maxNumber;
}

int main()
{
	cout << "Max : " << maxStep(9, 6) << endl;
	return 1;
}