[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)1904번, 01타일

문제 링크

1904번: 01타일

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

아래 표는 N의 숫자에 따른 만들어지는 타일의 종류와 개수를 표현한 것입니다.

N	종류	개수
1	1	1
2	11, 00	2
3	111, 001, 100	3
4	0000, 1100, 0011, 1111, 1001	5
5	10000, 00100, 00001, 11100, 11001, 10011, 00111, 11111	8
6	000000, 110000, 100100, 100001, 001100, 001001, 000011, 111100, 111001, 110011, 100111, 001111, 111111	13
7	0000000, 1000000, 0010000, 0000100, 0000001, 1110000, 1100001, 1100100, 1001100, 1000011, 0011100, 0011001, 0010011, 0000111, 1111100, 1111001, 1110011, 1100111, 1001111, 0011111, 1111111	21

 

표에서 개수를 살펴보면 규칙을 찾을 수 있습니다.

N을 개수를 뜻하는 단어로 생각하고 규칙을 쓰면

N = (N-1) + (N-2)입니다.

예를 들어 n=5일 때 n=4일때와 n=3일때를 더하면  N = 5 + 3으로 8입니다.

N의 최대값으로 1000000을 기준으로 메모이제이션 배열 크기를 1000001로 설정하였습니다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 타일 개수 구하는 함수 tile을 만들었습니다.

• check가 null이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• null인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• 위에 알고리즘 설명을 토대로 tile 함수를 작성하였습니다.

결과 코드

import java.io.*;
public class Main{
	static Integer[] check = new Integer[1000001];	//메모이제이션 배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	int n = Integer.parseInt(br.readLine());
    	checkInit();	//배열 초기화
    	System.out.println(tile(n));	//결과 출력
    	br.close();
	}
    //-------타일 개수 구하는 함수--------
	public static int tile(int n) {
		if(check[n]!=null)	//메모이제이션에 있으면 그 값 가져오기
			return check[n];
		check[n]=(tile(n-1) + tile(n-2))%15746;	//메모이제이션에 저장
		return check[n];	//결과 반환
	}
    //-------------배열 초기화 함수---------------
	public static void checkInit() {
		check[0] = 0;	//N=0일 때 0개
		check[1] = 1;	//N=1일 때 1개(1)
		check[2] = 2;	//N=2일 때 2개(00,11)
	}
}