백준 2193 이친수 동적계획법 활용 2가지 풀이 ( Java )

2193번: 이친수

 

- 2차원 배열 활용

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
 
        long[][] pinaryNumber = new long[n + 1][2];
 
        pinaryNumber[1][0] = 0;
        pinaryNumber[1][1] = 1;
        // 기저사례 세팅
 
        if (n >= 2) {
            pinaryNumber[2][0] = 1;
            pinaryNumber[2][1] = 0;
 
            for (int i = 3; i <= n; i++) {
 
                pinaryNumber[i][0] = pinaryNumber[i - 1][1] + pinaryNumber[i - 1][0];
                // 처음이 아니면 1과 0 모두 올 수 있다
 
                pinaryNumber[i][1] = pinaryNumber[i - 1][0];
                // 마지막에 1이 오면 앞에는 0만 올 수 있다
            }
        }
 
        long answer = pinaryNumber[n][0] + pinaryNumber[n][1];
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

- 1차원 배열 활용

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
 
        long[] pinaryNumber = new long[n + 1];
 
        pinaryNumber[1] = 1;
 
        // 기저사례 세팅
 
        if (n >= 2) {
            pinaryNumber[2] = 1;
 
            for (int i = 3; i <= n; i++) {
 
                pinaryNumber[i] = pinaryNumber[i - 1] + pinaryNumber[i - 2];
                // pinaryNumber[i] = i 자리 이친수의 갯수
                // pinaryNumber[i-1] = 마지막에 온 숫자가 0일 경우 그 전에 온 숫자는 알 수 없다
                // pinaryNumber[i-2] = 마지막에 온 숫자가 1일 경우 그 전에는 0만 올 수 있다. 그 전에 온 숫자는 알 수 없다
                // 그러니까 i-2일때는 01을 한 세트로 묶어서 생각한다
            }
        }
 
        long answer = pinaryNumber[n];
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

두 방식 모두 n으로 1일때를 간과하고 if (n >= 2) 처리를 안해줬다가 한참 헤맸다

아아 PS.. 그것은 헤맴의 연속..