1904번 01타일(자바, java) - 백준 문제풀이

처음에 dfs로 접근했다가 오류나고 피보나치형태를 띤다는 것을 알아내고 dp로 풀었는데도 재귀때문에 에러나고해서 for구문을 돌리게 되었다.

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

public class Main {
	static int count = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		int length = Integer.parseInt(st.nextToken());

		ArrayList<String> list = new ArrayList<>();
		
		String temp ;
		
		/*
		if(length == 1)
		{
			System.out.println("1");
			br.close();
			return;
		}
		else
		{
			temp = "1";
			dfs(list, temp, 1, length);
			
			temp = "00";
			dfs(list, temp, 2, length);
		}
		*/
		int[] fibo = new int[length+3];
		fibo[1] = 1;
		fibo[2] = 2;
		if(length == 1)
		{
			System.out.println("1");
			br.close();
			return;
		}
		else if(length == 1)
		{
			System.out.println("2");
			br.close();
			return;
		}
		else
		{
		
		for(int ii = 3; ii <= length ; ii++)
		{
		
			fibo[ii] = (fibo[ii - 1] + fibo[ii -2]) % 15746;
			
		}

			System.out.println(fibo[length]);
		}
		br.close();
		
	}
	
	public static int fibo(int n)
	{
		if(n == 1)
			return 1;
		else if( n == 2)
			return 2;
		else
			return fibo(n-1) + fibo(n-2);
	}
	
	public static void dfs(ArrayList<String> list, String temp, int start, int length)
	{
		if(start >= length)
		{
			if(temp.length() == length && !list.contains(temp))
			{
				list.add(temp);
				System.out.println(temp);
				count++;
			}
			return;
		}	
		
		for(int ii = start ; ii < length ; ii++)
		{
			dfs(list, temp+"1", ii+1, length );
			dfs(list, temp+"00", ii+2, length );
			
			
		}
	}
}