[백준/JAVA] 2193번: 이친수

🔺 문제

2193번: 이친수

 

 

🔺 코드

- 정답 1)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        long[][] D = new long[N + 1][2];
        D[1][1] = 1;    // 길이 1에서 1로  끝나는 이친수 개수
        D[1][0] = 0;    // 길이 1에서 0으로 끝나는 이친수 개수
        
        for(int i = 2 ; i <= N ; i++) {
            D[i][0] = D[i - 1][0] + D[i - 1][1];
            D[i][1] = D[i - 1][0];
        }
        System.out.println(D[N][0] + D[N][1]);
    }
}

✅ 해결 아이디어
✔ DP - 2차원 배열 점화식 활용
- D[i][0] : i 길이에서 끝이 0으로 끝나는 이친수 개수
- D[i][1] : i 길이에서 끝이 1로 끝나는 이친수 개수

 

 

- 정답 2)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        long[] D = new long[N + 1];
        D[0] = 0;
        D[1] = 1;
        
        for(int i = 2 ; i <= N ; i++) {
            D[i] = D[i - 1] + D[i - 2];
        }
        System.out.println(D[N]);
    }
}

 

 

💥 유의사항

- DP 배열을 long형으로 선언해야 함.

 ⇨ N이 45보다 큰 경우, int로 계산하면 올바른 결과를 얻지 못할 수 있으므로

      long형으로 선언해 정수 범위를 벗어나지 않도록 해야 함.

 

---

🔺 다른 풀이들

- 첫째 , 둘째 풀이과정 모두 설명 굿

[백준/2193/Java] 이친수

 

 

- 두 번째 풀이과정 설명

[알고리즘-JAVA] 백준 알고리즘 2193번 - 이친수

 

---

💬 느낀 점

두 번째 풀이는 직접 손으로 풀어보고 계산하고 규칙 찾아서 점화식 찾았는데

이렇게 뒷자리에서부터 역순으로 0 / 1이 나오는지 경우의 수를 나눠 규칙을 찾는 건지 몰랐다.

 

1회독	2회독	3회독	4회독	5회독
V	7/5

 

 

(+ 7/3 2회독)

위에 올린 2번째 풀이로 풀었는데

dp 배열을 int형으로 선언해서 틀렸었다ㅠ

그래도 점화식까진 생각해냈으니까 장족의 발전?!🤗

 

암튼 다음부터는 dp 배열 여유있게 long형으로 선언하고 가야겠다~~

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        long[] D = new long[N + 1];    // long형으로 해야 함!!!
        D[1] = 1;
        
        for(int i = 2 ; i <= N ; i++) {
            D[i] = D[i-1]+D[i-2];
        }
        
        System.out.println(D[N]);
    }
}
 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편