[백준] 2193 이친수 - 동적계획법(DP, Dynamic Programming) JAVA

https://www.acmicpc.net/problem/2193

코드설명

동적계획법(DP, Dynamic Programming) 문제입니다.

 

문제에서 유의해야할점입니다.

1. 문제에서 4%에서 계속 틀렸었는데, 이유는 int형 정답을 long 형으로 바꿨어야 했습니다.

이유는 최악의 경우 2^(90-2)개가 나옵니다. 최소의 경우에도 2^45가 나오고요. 이유는 N이 90인데, 만약 10___ 나머지 모두 0 인 경우, 101010101010.... (나머지 모두 10 인경우)로 생각해보면 알 수 있습니다.

 

2. 문제에서 기저사례로 처리할 부분은 마지막 한자리입니다.

만약, 1자리일경우 1과 0 둘다 가능하기에 2개의 경우를 반환합니다.

반면, 0자리일경우에는 단순히 1개를 만들었다고 생각하면 됩니다.

코드

처음에 상태를 2가지 사용하여 처리하여 잘못됨. 이렇게 할경우 최적 부분구조가 성립하지 않습니다.

number : 전 상태 isBeforeOne이 영향을 미치기에 메모이제이션 및 최적 부분 구조가 성립하지 않는다.

public static int number(boolean isBeforeOne, int n) {
    //기저사례 : 길이가 1일경우 1개만 두면 안됩니다. 이유는 1일떄 0과 1 둘다 들어갈 가능성이 존재하기에 그렇다.
    if(n <= 0) return 1;
    if(cache[n] != -1) return cache[n];

    int ret = 0;
    //만약 전의 숫자가 1이 아니라면, 1과 0 둘다 가능하다.
    if(isBeforeOne == false) {
        ret += number(true, n - 1); //1을 두는 경우.
        ret += number(false, n - 1); //0을 두는 경우
    }
    //만약 전의 숫자가 1이라면, 
    else if(isBeforeOne == true) {
        ret += number(false, n - 2); //0을 두는 경우
    }

    return cache[n] = ret;
}

 

 

정답코드입니다

package Main;

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

public class Main {
    public static int N, M;
    public static long answer = 0;
    public static int[] arr;
    public static long[] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N= Integer.parseInt(st.nextToken());
		cache = new long[N+1];
		Arrays.fill(cache, -1);
		answer = number2(N-2);
		System.out.println(answer);
	}
    
    public static long number2(int n) {
    	if(n == 1) return 2;
    	if(n <= 0) return 1;
    	if(cache[n] != -1) return cache[n];
    	
    	return cache[n] = number2(n - 2) + number2(n - 1);
    }
    
}