[Algorithm] 백준/Silver/2193. 이친수

하루입니다.

 

---

 

처음으로 혼자 DP 규칙 찾고 점화식 세우고 재귀함수까지 사용했다! 뿌듯한 포스팅. 

 

풀이방법

1. 냅다 숫자를 적기 시작했다.
2. 어? 그런데 규칙 찾으려면 숫자를 나열해야 하는데 숫자 규칙부터 찾아야 할 판인데 ;; ?
3. 어? 그런데 dp1은 2, dp2는 4, dp3은 8, dp4는 16 ... 두 배 규칙인가?
4. 어? 그런데 0과 1만 존재하니까 dp[n-1] 뒤에 0/1을 붙이면 되는 거 아닌가? 그러면 이진 트리(?)마냥 두 배로 뿔겠는데?
5. 어? 트리? 0과 1 트리? 애초에 0으로 시작되거나 11이 붙은 게 불가하다면, 그 뒤에 애들도 불가한 거 아닌가? 그러면 이미 빨간 줄 친 애들은 처리할 필요가 없겠는데?
6. 그러면 파란색 애들 뒤에만 0/1을 붙여보자!  

 

 

 

 

---

 

 

코드 변천사

사실 크게 변화한 건 없고, 배열을 어디서 선언하느냐의 차이였다. 두 경우에 차이가 있긴 한데, 아직 내 수준으로는 뭐가 더 낫다거나 이래서 차이가 난다! 라고 설명하긴 어렵당 🥲

 

첫 번째 : 최대 n이 90까지라서 new int[91]을 아예 static하게 선언했다. 

코드 보기

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

class Main {    
    static long dp[] = new long[91];
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        
        int n = Integer.parseInt(br.readLine());
        System.out.println(pn(n));
    }
    
    public static long pn(int n) {
        if(dp[n] == 0) {
            dp[n] = pn(n-1) + pn(n-2);
        }
        return dp[n];
    }
}

 

 

두 번째 : n을 내부에서 받고 new int[n+1]을 main 내부에서 선언(?)했다.

코드 보기

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

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

        int n = Integer.parseInt(br.readLine());
        dp = new long[n+1];

        for(int i = 0; i < n + 1; i++) {
            dp[i] = -1;
        }

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

        System.out.println(pn(n));
    }

    public static long pn(int n) {
        if(dp[n] == -1) {
            dp[n] = pn(n-1) + pn(n-2);
        }
        return dp[n];
    }
}

 

 

---

 

여담.

재귀와 스택 ... 혼자 했으면 자료구조 내팽개치고 알고리즘 들어가서 재귀 개념 이해하는 데 시간이 훨씬 많이 걸렸을 거 같다(사실 내가 잘 이해한 지도 모르겠지만). 그런데 같이 스터디 하는 분 덕분에 자료구조를 한번이라도 짚고 넘어갈 수 있었고, 그래서 이해가 조금은 더 빠르게 된 거 같다. 나도 열심히 해서 이끌고 알려줄 수 있는 사람이 되어야겠다. 그래도 뭔가 오늘 ... 최빈수 찾기에서 탈탈 털렸지만 성장한 게 보여서 뿌듯한 하루였다.

 

 

---

 

 

깃허브가 궁금하시다면

https://github.com/mjkim856/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/2193.%E2%80%85%EC%9D%B4%EC%B9%9C%EC%88%98

 

오늘도 감사합니다!

https://st-lab.tistory.com/123

https://st-lab.tistory.com/94