이소영

1️⃣ [BOJ] 피보나치 수2

❓ 피보나치 수(Fibonacci Numbers)란?

✔ Java

[BOJ] 피보나치 수2

피보나치 수(Fibonacci Numbers)란?

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

Java

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        System.out.println(main.solution(n));
    }
    
    public long solution(int n) {
        long[] memo = new long[n+1];
        
        memo[0] = 0;
        memo[1] = 1;
        
        for(int i = 2; i <= n; i++) {
            memo[i] = memo[i-1] + memo[i-2];
        }
        
        return memo[n];
    }
}
Java
복사

Python

n = int(input())
memo = [0, 1]
for i in range(2, n+1):
    memo.append(memo[i-1] + memo[i-2])
print(memo[n])
Python
복사

 실행결과

파도반 수열

파도반 수열이란?

시계 방향으로 이동하면서 기존 삼각형들과 밑변을 공유하는 새로운 정삼각형을 그리는 과정을 반복할 때, 그려지는 정삼각형들의 변

접근 방법

찾아낸 점화식 : memo[i] = memo[i-2] + memo[i-3]

Java

import java.util.Scanner;

public class Main {

	private long[] padovan(int size) {
		long[] sequence = new long[size+1];
		
		sequence[0] = sequence[1] = sequence[2] = 1;
		
		for (int i = 3; i <= size; i++) {
			sequence[i] = sequence[i-2] + sequence[i-3];
		}
		
		return sequence;
	}

	public static void main(String[] args) {
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		long[] p = main.padovan(100);
		
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt();
			System.out.println(p[N-1]);
		}
	}
}
Java
복사

Python

def padovan():
    p = [1, 1, 1]
    for i in range(3, 100):
        p.append(p[i-2] + p[i-3])
    return p
    
p = padovan()
T = int(input())

for t in range(0, T):
    n = int(input())-1
    print(p[n])
Python
복사

 실행결과

도둑질

접근 방법

연속된(인접한) 집이 하나라도 털리게 되는 경우 경보가 울리게 됨

최댓값 구하기

1번 집을 시작으로 인접한 집이 털리지 않도록 money를 담아주기

1번 집이 아닌 2번 집을 시작으로 인접한 집이 털리지 않도록 money를 담아주기

Java

public class Solution { // 도둑질

	public static void main(String[] args) {
		Solution main = new Solution();

		int[] money = { 1, 2, 3, 1 };
		System.out.println(main.solution(money));
	}

	private int solution(int[] money) {
		int answer = -1;
		
		// 첫 집부터 털었을 때 메모 배열(마지막집은 털지 x)
		int[] dp1 = new int[money.length];
		// 첫 집을 털지 않았을 때 메모 배열
		int[] dp2 = new int[money.length];
		
		// 시작 값
		dp1[0] = dp1[1] = money[0];
		dp2[0] = 0;
		dp2[1] = money[1];
		
		for (int i = 2; i < dp2.length; i++) {			
			if(i < dp1.length-1) {  // 마지막 집을 털지 않기 위해 조건문 작성
				dp1[i] = Math.max(dp1[i-1], dp1[i-2] + money[i]);
//				answer = Math.max(dp1[i], answer);
			}
			dp2[i] = Math.max(dp2[i-1], dp2[i-2]+money[i]);
//			answer = Math.max(dp2[i], answer);
		}
		
		answer = Math.max(dp1[dp1.length-2], dp2[dp2.length-1]);
		
		return answer;
	}

}
JavaScript
복사

 실행 결과