DP - 2193. 이친수

문제

www.acmicpc.net/problem/2193

 

잠깐만

한자리수 이친수 부터 여섯자리수 이친수까지 직접 계산해보세요. 규칙이 보일거에요

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int target = Integer.parseInt(st.nextToken()); 
		
		long f0 = 0;
		long f1 = 1;
		
		for (int n = 2; n <= target; n++) {
			long fn = f0 + f1;
			f0 = f1;
			f1 = fn;
		}
		
		System.out.print(f1);
	}
}

2748. 피보나치 수 2 문제의 답 그대로 가져왔습니다;;;;

설명

여섯자리 이친수까지 직접 계산해봤나요?

안했으면 해보고 오세요 빨리요~

 

저는 직접 그려봤는데, 규칙이 보이더라구요. 보이시죠?

이친수 개수는 피보나치입니다. 왜냐구요??

 

다섯자리수 이친수까지 같이 한번 살펴보죠

규칙이 보이죠????

다섯자리수의 100으로 시작하는 이친수는 네자리수 이친수와 패턴이 같고,

다섯자리수의 101로 시작하는 이친수는 세자리수 이친수와 패턴이 같아요.

 

여섯자리 이친수를 같이 볼까요?

여섯자리 이친수의 100으로 시작하는 이친수는 다섯자리수 이친수의 패턴과 같고

여섯자리 이친수의 101로 시작하는 이친수는 네자리수 이친수의 패턴이 같습니다.

 

따라서, 피보나치와 같이 풀면 됩니다.