[BOJ 1904] 01타일 (Java)

문제

https://www.acmicpc.net/problem/1904

1904번: 01타일

 

풀이

타일을 0과1로 표현했을 뿐이지 아래와 동일한 문제이다.

dp[1] = 1

dp[2] = 2

dp[3]부터는 아래 점화식을 따른다.

dp[i] = dp[i-1]+ dp[i-2]

 

2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 2 x n 타일링 (Java)

[프로그래머스] 2 x n 타일링 (Java)

2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 멀리 뛰기 (Java)

[프로그래머스] 멀리 뛰기 (Java)

 

소스코드

package dp;

import java.util.Scanner;

public class BOJ1904 {

    public static void main(String[] args) {
        // N = 1, 1
        // N = 2, 00, 11
        // N = 3, 100, 001, 111
        // N = 4, 1001, 0011, 1111, 0000, 1100

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] rs = new int[n+1];
        for(int i = 1; i <= n; i++){
            if(i == 1){
                rs[i] = 1;
                continue;
            }
            if(i == 2) {
                rs[i] = 2;
                continue;
            }
            rs[i] = (rs[i-1] + rs[i-2])%15746;
        }
        System.out.println(rs[n]);
    }
}