[Algorithm] ๐Ÿงบ๋ฐฑ์ค€ 2193 ์ด์นœ์ˆ˜

HaJingJingยท2021๋…„ 7์›” 19์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
95/119

0. ๋ฌธ์ œ

0๊ณผ 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ์ˆ˜๋ฅผ ์ด์ง„์ˆ˜๋ผ ํ•œ๋‹ค. ์ด๋Ÿฌํ•œ ์ด์ง„์ˆ˜ ์ค‘ ํŠน๋ณ„ํ•œ ์„ฑ์งˆ์„ ๊ฐ–๋Š” ๊ฒƒ๋“ค์ด ์žˆ๋Š”๋ฐ, ์ด๋“ค์„ ์ด์นœ์ˆ˜(pinary number)๋ผ ํ•œ๋‹ค. ์ด์นœ์ˆ˜๋Š” ๋‹ค์Œ์˜ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•œ๋‹ค.

์ด์นœ์ˆ˜๋Š” 0์œผ๋กœ ์‹œ์ž‘ํ•˜์ง€ ์•Š๋Š”๋‹ค.
์ด์นœ์ˆ˜์—์„œ๋Š” 1์ด ๋‘ ๋ฒˆ ์—ฐ์†์œผ๋กœ ๋‚˜ํƒ€๋‚˜์ง€ ์•Š๋Š”๋‹ค. ์ฆ‰, 11์„ ๋ถ€๋ถ„ ๋ฌธ์ž์—ด๋กœ ๊ฐ–์ง€ ์•Š๋Š”๋‹ค.
์˜ˆ๋ฅผ ๋“ค๋ฉด 1, 10, 100, 101, 1000, 1001 ๋“ฑ์ด ์ด์นœ์ˆ˜๊ฐ€ ๋œ๋‹ค. ํ•˜์ง€๋งŒ 0010101์ด๋‚˜ 101101์€ ๊ฐ๊ฐ 1, 2๋ฒˆ ๊ทœ์น™์— ์œ„๋ฐฐ๋˜๋ฏ€๋กœ ์ด์นœ์ˆ˜๊ฐ€ ์•„๋‹ˆ๋‹ค.

N(1 โ‰ค N โ‰ค 90)์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, N์ž๋ฆฌ ์ด์นœ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— N์ž๋ฆฌ ์ด์นœ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก ํ•˜๋‚˜์”ฉ ๊ตฌํ•˜๋‹ค ๋ณด๋ฉด ํ”ผ๋ณด๋‚˜์น˜์ˆ˜์—ด๊ณผ ๊ฐ™๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋จ
๐Ÿ’ก ํ”ผ๋ณด๋‚˜์น˜์ˆ˜์—ด ์ด์šฉํ•ด์„œ ๋ฌธ์ œ ํ•ด๊ฒฐ

2. ํ•ต์‹ฌ ํ’€์ด

  1. ํ”ผ๋ณด๋‚˜์น˜์ˆ˜์—ด ์ด์šฉํ•ด์„œ ๋ฌธ์ œ ํ•ด๊ฒฐ
for(int i=2; i<n; i++) {
	dp[i] = dp[i-1] + dp[i-2];
}

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class DP_19 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		if(n == 0 || n == 1) {
			System.out.println(n);
			return;
		}
		
		long[] dp = new long[n];
		
		dp[0] = 1;
		dp[1] = 1;
		
		for(int i=2; i<n; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		
		System.out.println(dp[n-1]);
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ
long์„ ๊ณ ๋ คํ•ด์„œ ์งœ์•ผํ•จ..

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€