DP 연습문제 1 - 아파트 색칠

Java

DP 연습문제 1 - 아파트 색칠

문제

아파트를 각 층별로 파란색 또는 노란색 페인트로 칠하되 다음과 같은 규칙으로 칠하려고 한다.

노란색은 인접한 두 층에 연속하여 사용할 수 있다.

파란색은 인접한 두 층에 연속하여 사용할 수 없다.

이와 같은 규칙으로 층의 아파트를 칠할 수 있는 방법의 수를 f(n)이라 하면 다음 그림과 같이 f(1) = 2, f(2) = 3 이다.

f(8)을얼마인가?

접근 방법 - 무지성

처음 1층에는 노랑(Y) 파랑(B) 2개가 있다.

Y | B (2)

이제 2층부터, 1층의 Y B에 Y와 B를 가능한 올려본다고 생각한다.
그렇다면 Y위에는 Y B가 올라갈 수 있으며(2), B 위에는 Y 밖에 올라오지 못한다.(1)

Y | B | Y (3)
  Y   | B (2)

3층에도 마찬가지로 가장 최 상단인 Y B Y에 Y B를 가능한 올려본다.
첫번째 Y에는 Y B, 두번째 B에는 Y, 세번째 Y에는 Y B가 올라온다.

Y B | Y | Y B (5)
 Y  | B |  Y  (3)
    Y   |  B  (2)

위와 같이 반복하다보면 f(n) = f(n - 1) + f(n - 2) 발견 할 수 있다.

접근 방법 - 점화식

위 방법을 응용하여 점화식을 세워보자.
역시 제일 위 층에 Y 혹은 B를 쌓아 올린다고 생각하자.
현재 층이 N이면 N - 1층까지 세운 아파트 위에 Y와 B를 올리면 된다.
하지만 문제 조건에서 B는 연속으로 세울 수 없므로, 제일 윗 층에 B가 올려면 반드시 아랫층에는 Y가 와야한다.

따라서, F(N) = 제일 위층에 Y가 올 때 F(N-1) + 제일 위층에 B가 올 때 F(N-2)가 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int n = 8;
    	int[] f = new int[n + 1];
    	f[1] = 2;
    	f[2] = 3;
    	
    	for(int i = 3; i <= n; i++) {
    		f[i] = f[i - 1] + f[i - 2];
    	}
    	
    	System.out.println(f[n]);
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

DP 점화식의 기본 문제

개선할 점

없