3 또는 2로 나누거나, 아니면 1을 빼는 3가지 연산만을 이용해서 1로 만들면 된다.


2 -> 2-1 or 2/2 (1단계이므로 1)

10 -> 9 -> 3 -> 1 (4단계이므로 4)


DP 문제에 속하지만 별로 DP로 해결하는 방법이 생각나지는 않아서 3-트리 형식으로 문제를 풀었다.


#include <iostream>
#include <algorithm>

using namespace std;

int g_nDepth;

int MakeOne(int nVal, int nDepth)
{
	if (nVal <= 1)
		return nDepth - 1;

	if (g_nDepth <= nDepth)
		return nDepth;

	int nRet = 0x7FFFFFFF;

	//! divide 3
	if (nVal % 3 == 0)
		nRet = min(MakeOne(nVal / 3, nDepth + 1), nRet);
	//! minus 1
	nRet = min(MakeOne(nVal - 1, nDepth + 1), nRet);
	//! divide 2
	if (nVal % 2 == 0)
		nRet = min(MakeOne(nVal / 2, nDepth + 1), nRet);

	g_nDepth = nRet;

	return nRet;
}

int main()
{
	g_nDepth = 0x7FFFFFFF;

	int nCnt = 0;

	scanf("%d", &nCnt);
	printf("%d\n", MakeOne(nCnt, 1));

    return 0;
}


처음에는 최소 depth에 대한 내용이 없었어서 시간이 과도하게 오래 걸리는 문제가 있었는데, depth 관련 부분만 추가해서 문제를 해결했다.

'Programming > C,C++' 카테고리의 다른 글

[BOJ] 2579. 계단 오르기  (0) 2018.01.15
[BOJ] 1463. 1로 만들기  (0) 2018.01.15
[BOJ] 1003. 피보나치 함수  (0) 2018.01.15
[Codility] TieRopes  (0) 2018.01.07
[Codility] MaxNonoverlappingSegments  (0) 2018.01.07
[LeetCode] 100. Same Tree  (0) 2018.01.03

+ Recent posts