문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

문제

유토피아 나무는 매년 2번의 주기로 성장한다. 봄에는 2배, 여름에는 1미터 성장한다.
높이가 1인 유토피아 나무가 봄이 시작될때 심어진다. 그러면 n 주기 후에 나무는 얼마나 자랄까?

Example

n = 5

Period	Height
0	1
1	2
2	3
3	6
4	7
5	14

Function Description

utopianTree 함수를 완성해라.
utopianTree 함수는 아래와 같은 매개변수를 가지고 있다.

• int n: 시뮬레이션할 성장 주기의 수

Return

• int: 주어진 성장 주기 후의 나무 높이

Constraints

0 <= n <= 60

풀이

Dynamic Programming으로 해결할 수 있다.

점화식을 계산하기 전에 n이 0이면 1을 리턴할 수 있게 한다. 왜냐하면 n이 0이면 점화식을 계산하기 필요없기 때문이다.

if(n == 0){
	return 1;
}

이제 점화식을 만든다. Integer 배열을 n + 1만큼 생성하고, 0 index에 1을 할당한다. 그리고 height의 길이만큼 반복문을 통해 순회한다. 순회하면서 해당 index가 홀수는 봄이라서 이전 값에 *2, 짝수는 여름이라서 이전 값에 +1을 해서 해당 index에 할당한다.

int[] height = new int[n + 1];

height[0] = 1;

for(int i = 1; i < height.length; i++){
	if(i % 2 == 1){
		height[i] = height[i - 1] * 2;
	}else{
		height[i] = height[i - 1] + 1;
	}
}

점화식을 통해 값이 다 채워졌다면 index n의 값을 반환하면 된다.

return height[n];

전체 코드

public static int utopianTree(int n) {
	if(n == 0){
		return 1;
	}

	int[] height = new int[n + 1];

	height[0] = 1;

	for(int i = 1; i < height.length; i++){
		if(i % 2 == 1){
			height[i] = height[i - 1] * 2;
		}else{
			height[i] = height[i - 1] + 1;
		}
	}

	return height[n];
}