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

문제 링크

11726번: 2×n 타일링

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

 

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

 

이 문제에 핵심은

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

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

 

배열

 

DP : 메모이제이션 배열

 

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

 

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

 

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

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

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

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

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

규칙은f(n) = f(n-1) + f(n-2)

 

문제에 해결알고리즘은

1. n을 입력받습니다.

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

 

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

• tiling는 규칙을 통한 재귀를 반복하여 경우의 수를 구합니다.
• init은 DP[1] = 1, DP[2] = 2로 초기화 해줍니다.

 

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

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int n, div = 10007;
	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
        //--------입력값 처리-----------
    	n = Integer.parseInt(br.readLine());
    	DP_init();		//메모이제이션 초기화
    	int result = tiling(n);	//경우의 수 함수 실행
    	bw.write(result+ "\n");		//경우의 수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //--------경우의 수 구하는 함수------
    public static int tiling(int n) {
    	if(n==0)
    		return 0;
    	if(DP[n]!= 0) {
    		return DP[n];
    	}
    	DP[n] =  tiling(n-1) + tiling(n-2);		//규칙 재귀로 적용
    	return DP[n]%div;		//10007로 나누어서 나머지 구하기
    }
    //----메모이제이션 초기화 함수-------
    public static void DP_init() {
    	DP[1] = 1;
    	DP[2] = 2;
    	return;
    }
    
}