[백준] 2193번: 이친수 - Java, 자바

xxx-sj·2023년 8월 29일

알고리즘

목록 보기

36/46

문제접근

먼저 자릿수에 대한 개념을 잡기 위해서 이전 글을 참고하고 오면 이해하기 쉽습니다.
이전 글

이 전에 풀던DP와 같은 풀이로 푼다. 자릿수에 해당하는 자릿값으로 문제를 푸는데 dp[digit][val]
여기서 자릿값은 0 or 1, 2개만 가능하다.
1. 다음 조건으로는 시작이 0 으로 시작하지 않는다는 점.
2. 1이 연속으로 두 번 나타나지 않는다는 점.
이 조건들을 조합해보면 아래와같은 재귀함수를 만들 수 있다.

digit[자릿수] 가 1일때는 digit[digit][val]를 반환한다. [종료시점]
dp[digit][val] == null 일 때
- val이 1일때는 뒤에 올 수 있는 수는 0밖에 없으므로 recur(digit - 1, 0);
- val이 0일때는 뒤에 0 or 1이 올수 있기 때문에 recur(digit - 1, 0) + recur(digit -1 , 1) 이 된다.
  코드로 보면 아래와 같다.

전체코드 (top-down)

package date_2023_08_16.DP_2193;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Long[N + 1][2];

        dp[1][0] = dp[1][1] = 1L;

        System.out.println(recur(N, 1));
    }

    static Long recur(int digit, int val) {

        if(digit == 1) {
            return dp[digit][val];
        }

        if(dp[digit][val] == null) {
            if(val == 1) {
                dp[digit][val] = recur(digit - 1, 0);
            } else {
                dp[digit][val] = recur(digit - 1, 0) + recur(digit - 1, 1);
            }
        }

        return dp[digit][val];
    }
}

코드 상세

N을 입력받는다.
- 입력받은 N으로 배열을 생성한다.
- 이 때 이차원 배열은 Long을 사용한다. 2^90이어 값이 넘어갈 수 있기 때문에..?
- N + 1 인 이유는 인덱스가 0 부터 시작하기 때문이고, 두 번째 크기가 2인 이유는 0 or 1 두개 만 들어가기 때문에.

static Long dp[][];

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
dp = new Long[N + 1][2];

초기값을 설정한다.

dp[1][0] = dp[1][1] = 1L;

재귀함수를 선언한다.
- 종료조건은 digit == 1 일때
- 아직 배열의 값이 초기화되지 않았다면
  - val == 1 일때는 뒷 값으로 0 밖에 오지 못함.
  - val == 0 일때는 뒷 값으로 0, 1 둘다 가능.

static Long recur(int digit, int val) {

    if(digit == 1) {
        return dp[digit][val];
    }

    if(dp[digit][val] == null) {
        if(val == 1) {
            dp[digit][val] = recur(digit - 1, 0);
        } else {
            dp[digit][val] = recur(digit - 1, 0) + recur(digit - 1, 1);
        }
    }

    return dp[digit][val];
}

재귀함수를 호출한다.
- N,1 만 호출하는 이유는 첫번 째 값이 1밖에 오지 못하기 때문이다.

System.out.println(recur(N, 1));

bottom-up

이제는 bottom-up으로 풀어보도록 하자.
어떠한 자릿수 N에 올 수 있는 수는 0 or 1 일 것이다. 그렇다면 N - 1에는 어떻게 와야하는가?
N에서 0 일때는 1 or 0 둘 다 올 수 있지만 1일 경우는 0밖에 오지 못한다는 것을 알 수 있다.

if (val == 0) {
	dp[digit][val] = dp[digit - 1][0] + dp[digit -1][1];
} else {
//val == 1
	dp[digit][val] = dp[digit - 1][0];
}

bottom-up 전체코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Long[N + 1][2];

        dp[1][0] = dp[1][1] = 1L;

        bottom_up(N);

			//1만 하는 이유는 N 자리 즉, 가장 앞자리에는 0이 올수 없기 때문에.
        System.out.println(dp[N][1]);
    }


    static void bottom_up(int N) {

        for(int i = 2; i <= N; i++) {
            for(int j = 0; j <= 1; j++) {

                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] + dp[i - 1][1];
                } else if (j == 1){
                    dp[i][j] = dp[i - 1][0];
                }
            }
        }
    }

}

여담

이친수를 적다보면 규칙이 하나보이는데,

dp[1] = 1;
dp[2] = 10;
dp[3] = 100, 101;
dp[4] = 1000, 1010, 1001;
dp[5] = 10000, 10100, 10010, 10001, 10101;

dp[N]에 대하여 dp[N -1] 수 뒤에 0을 붙인 값 +
dp[N]에 대하여 dp[N - 2] 수 뒤에 01 을 붙인 값을 더한게 dp[N]에 된다는 것이다..

dp[3]을 먼저 보면 dp[1] = 1에 01 을 붙인 [101]과 dp[2]에 0을 붙인 [100]이 곧 dp[3]이 된다.
다시,
dp[4] 에서 dp[2]에 01을 붙인 [1001], dp[3]에 0을 붙인 [1000, 1010] 이 곧 dp[4]가 된다.
즉,
dp[N] = dp[N -1] + dp[N -2]; 가 성립한다.
이렇게 1차원배열로도 문제를 풀 수 있다.