POJ - 2942: 사탕 먹 기.

이 문제 의 관건 은 '엄마 가 명 명 에 게 매일 한 조각 이나 초콜릿 두 조각 을 먹 을 수 있다 고 알려 주 었 다' 는 것 이다. 물론 내 가 한 말 은 쓸데없는 혐의 가 있다.
하지만 부인 할 수 없다. 이 말 은 정말 중요 하 다.매일 한 조각 또는 두 조각 을 먹 을 수 있다 면 이렇게 가설 을 할 수 있 습 니 다. 만약 에 제 가 i 일 에 j 번 째 사탕 을 먹었다 고 가정 하면 i + 1 일 에 j + 1 또는 j + 2 번 째 사탕 을 먹 었 습 니 다.중요 한 것 은 제 가 i 일 에 j 번 째 사탕 을 먹 는 방안 의 수량 이 바로 제 가 i + 1 일 에 j + 1 과 j + 2 개의 사탕 을 먹 는 것 과 같 습 니 다.
왜 냐 고 물 어 보 겠 지만그럼 제 가 이렇게 질문 을 하 겠 습 니 다. 제 가 i + 1 일 에 사탕 이 하나 밖 에 없 었 습 니 다. 그러면 제 가 남 은 가설 은 m 개의 사탕 을 k 일 에 다 먹 어야 한 다 는 것 과 제 가 i + 1 일 에 사탕 이 2 개 밖 에 없 는 것 이 아 닙 니까? 그러면 제 가 남 은 m - 1 개의 사탕 을 n 일 에 다 먹 어야 한 다 는 것 은 두 가지 다른 방안 입 니까?바로 그 렇 기 때문에 우 리 는 순서대로 밀 수 있다.이 알고리즘 세그먼트 가 져 오기:
1. n 이 1 이면 1 을 되 돌려 줍 니 다.
2. n 이 2 라면 2 로 돌아 가기;
3. n 이 2 보다 큰 숫자 라면 n - 1 과 n - 2 의 합 을 되 돌려 줍 니 다.
private static int getCount(int n) {
		if (n == 1) {
			return 1;
		} else if (n == 2) {
			return 2;
		} else {
			return getCount(n -1) + getCount(n- 2);
		}
	}

------------------------------------------------- AC CODE -----------------------------------------------
import java.util.Scanner;

public class Main {

	private static int getCount(int n) {
		if (n == 1) {
			return 1;
		} else if (n == 2) {
			return 2;
		} else {
			return getCount(n -1) + getCount(n- 2);
		}
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println(getCount(in.nextInt()));
	}

}

좋은 웹페이지 즐겨찾기