돌다리 건너기

코드

public class 돌다리건너기 {
	static int[] dy;
	static int[] memo;
	
	static int cnt = 0;
	
	public static void main(String[] args) {
		int goal = 10; // 돌다리 개수
		goal +=1; //1개를 더한다
		
		dy = new int[goal+1];
		memo = new int[goal+1];
		
		long start = System.nanoTime();
		System.out.println("answer = " +dy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDyMemo(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
	}

	private static int dy(int goal) {
		dy[1] = 1;
		dy[2] = 2;
		for(int i=3;i<=goal;i++,cnt++) {
			dy[i] = dy[i-1]+dy[i-2];
		}
		return dy[goal];
	}
	
	static int noDy(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else return noDy(goal-1)+noDy(goal-2);
	}
	
	static int noDyMemo(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else if(memo[goal]>0) return memo[goal];
		else return memo[goal]=noDyMemo(goal-1)+noDyMemo(goal-2);
	}
}

---

결과

answer = 144
9
765600
answer = 144
177
47600
answer = 144
19
21900

---

계단 같은 경우는 계단에 도착한게 도착지지만, 

돌다리의 경우 건너편을 건너기 위한 돌다리 개수를 받았기 때문에 최종 돌다리가 목적지가 아니라 +1 한 건너편이 목적지다