[ 백준 ] 1904번 : 01타일 - (c++/c, java/자바, python/파이썬)

• 문제

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

---

• 알고리즘 ( 접근 )

N = 1 -> ans : 1 ( 1 )

N = 2 -> ans : 2 ( 00 , 11 )

N = 3 -> ans : 3 ( 001, 100, 111)

N = 4 -> ans : 5 ( 0011, 1111, 0000, 1100, 1001)

N = 5 -> ans : 8 ( 00111, 10011, 11001, 11100, 00001, 10000, 00100, 11111 )

 

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

즉, 피보나치 수열로 풀 수 있다.

---

• 풀이 - C++ / C

#include <iostream>

using namespace std;

int dp[1000001];
int n;

int main(void)
{
	cin >> n;
	dp[1] = 1; dp[2] = 2;
    
	for (int i = 3; i <= n; i++)
		dp[i] = dp[i - 2] % 15746  + dp[i - 1] % 15746;
	cout << dp[n] % 15746;

	return 0;
}

• 풀이 - JAVA

import java.util.Scanner;

public class Main
{
    public static int dp[] = new int[1000001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        dp[1] = 1; dp[2] = 2;
        for(int i = 3; i <= n; i++)
            dp[i] = dp[i-2] % 15746 + dp[i-1] % 15746;
        System.out.println(dp[n] % 15746);
    }
}

• 풀이 - PYTHON

n = int(input())
dp = [0 for _ in range(1000001)] 

dp[1] = 1
dp[2] = 2

for i in range(3, n+1):
    dp[i] = (dp[i-1]+ dp[i-2]) % 15746

print(dp[n])