[백준] code.plus(다이나믹 프로그램 part 1,JAVA)11727번, 2×n 타일링 2

문제 링크

11727번: 2×n 타일링 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

다이나믹 프로그램

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

 

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 2x1, 1x2, 2x2 타일만 사용할 수 있습니다.

2. 2×n이 직사각형을 채우는 방법의 수를 결과로 출력합니다.

 

배열

 

DP : 메모이제이션 배열

 

재귀문과 DP 배열을 이용하여 방법의 수를 구하였습니다.

 

이 문제의 규칙을 발견하면 정말 쉽게 풀 수 있는 문제입니다.

 

n = 1일 때 경우의 수는 1개

n = 2일 때 경우의 수는 3개

n = 3일 때 경우의 수는 5개

n = 4일 때 경우의 수는 11개

n = 5일 때 경우의 수는 21개

n = 6일 때 경우의 수는 43개

n = 7일 때 경우의 수는 85개n = 8일 때 경우의 수는 171개

 

규칙은

n이 짝수일 때

f(n) = f(n-1) * 2 +1

n이 홀수일 때f(n) = f(n-1) * 2 -1

 

문제에 해결알고리즘은

1. n을 입력받습니다.

2. 재귀를 통해 위에 규칙을 적용하여 나온 결과를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 재귀를 통해 규칙을 적용하는 tiling함수를 만들었습니다.
• BufferedWriter에 경우의 수를 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• tiling는 규칙을 통한 재귀를 반복하여 경우의 수를 구합니다.

 

※문제에서 10007를 나눈 나머지를 결과로 출력해야 되는 것을 기억하고 사용해주셔야 합니다.!

 

결과 코드

import java.io.*;
public class Main{
	public static int[] DP = new int[1001];	//메모이제이션 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-------입력값 저장 및 함수 실행-------
    	int N = Integer.parseInt(br.readLine());
    	int result = tiling(N);
    	bw.write(result + "\n");	//경우의 수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //------타일 경우의 수 구하는 함수---------
    public static int tiling(int n) {
    	if(n == 1)		//f(1) = 1
    		return 1;
    	
    	if(DP[n] != 0)	//한 번 수행한 연산이면 메모이제이션에 저장된 내용 가져오기
    		return DP[n];
    	if(n % 2 == 0){		//n이 짝수일 때
    		DP[n] = (tiling(n-1) * 2 + 1)%10007;
    	}else		//n이 홀수일 때
    		DP[n] = (tiling(n-1) * 2 - 1)%10007;
    	return DP[n];		//결과 반환
    }
}