[백준/JAVA] 1904번: 01타일

🔺 문제

1904번: 01타일

 

🔺 코드

- 풀이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());
        int[] dp = new int[N + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            if(i == 1 || i == 2 || i == 3) {
                dp[i] = i;
            } else {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
            }
        }
        
        System.out.println(dp[N]);
    }
}

✅ 해결 아이디어
✔ DP → 피보나치 수열

 

 

- 풀이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());
        int[] dp = new int[1_000_001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        
        for(int i = 4 ; i <= N ; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        }
        
        System.out.println(dp[N]);
    }
}

dp 사이즈를 N + 1로 했다간 런타임 에러 (ArrayIndexOutOfBounds)가 뜬다.

 

---

🔺 다른 풀이들

- 멋진 설명 과정과 코드... 항상 감사하는 중...

[백준] 1904번 : 01타일 - JAVA [자바]

 

 

- Top-Down 방식도!

[알고리즘 PS] 백준 1904번 01 타일 자바 문제 풀이

 

 

- 메모이제이션 설명 감사..

[백준][JAVA알고리즘]1904번 풀이(01타일) - 초보도 이해하는 풀이

---

💬 느낀 점

흠... DP 문제가 이 정도 난이도로만 나와준다면 고마울텐데...

 

 

 

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

---

(참고)

✔ 런타임 에러 부분

글 읽기 - 자바 런타임 에러