[백준] code.plus(다이나믹 프로그램 part 1,JAVA)2193번, 이친수

문제 링크

2193번: 이친수

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

 

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

 

이 문제에 핵심은

1. 이진수가 1부터 시작 및 11로 연속된 부분 문자열을 가지지 않는다.

2. 입력값 자릿수만큼 이친수로 나타낼 수 있는 경우의 수를 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

 

DP 배열을 이용하여 입력값의 경우의 수를 구하였습니다.

 

이 문제는 각 자리수를 만들어보면 규칙을 찾을 수 있습니다.

 

N = 1일 때 경우의 수

{1}

1개

 

N = 2일 때 경우의 수

{10}

1개

 

N = 3일 때 경우의 수

{100, 101}

2개

 

N = 4일 때 경우의 수

{1010, 1001, 1000}

3개

 

N = 5일 때 경우의 수

{10100, 10101, 10010, 10001, 10000}

5개

 

N = 6일 때 경우의 수

{101010, 101001, 101000, 100101, 100100, 100010, 100001, 100000}

8개

 

 

입력값 1~6까지의 경우를 표로 만들어보았습니다.

	경우의 수
1	1
2	1
3	2
4	3
5	5
6	8

표에 내용을 살펴보면 규칙이 존재합니다.

 

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

 

n = 4일 때

f(4) = f(3) + f(2) = 2 + 1 = 3

 

규칙을 이용하면 경우의 수를 다 만들지 않고 구할 수 있습니다.

 

문제에 해결알고리즘은

1. DP[0]과 DP[1]을 초기화해주었습니다.

2. 입력값만큼 규칙대로 DP[]를 구성합니다.

3. DP[N]을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• DP[0]과 DP[1]을 초기화하는 init 함수를 만들었습니다.
• 이친수의 경우의 수를 구하는 pinaryNumber 함수를 만들었습니다.
• BufferedWriter에 DP[N]을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• init는 DP[0], DP[1]을 초기화 하였습니다.
• pinaryNumber는 재귀를 통해 DP[]를 구성하였습니다.

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static long[] DP = new long[91];		//메모이제이션 배열
    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());
    	init();		//DP 초기화
    	bw.write(pinaryNumber(N) + "\n");		//함수 결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //이친수 경우의 수 구하는 함수
    public static long pinaryNumber(int n) {
    	if(n==0)		//n이 0일 때
    		return DP[0];
    	if(DP[n]!=0)	//이미 연산하여 메모이제이션에 값이 존재할 때
    		return DP[n];
    	DP[n] = pinaryNumber(n-1) + pinaryNumber(n-2);	//규칙 적용
    	return DP[n];		//값 반환
    }
    public static void init() {
    	DP[0] = 0;		//DP[0]의 경우의 개수는 없다.
    	DP[1] = 1;		//DP[1]의 경우의 개수는 {1}로 1개이다.
    }
}