127. 1904 (01타일)

문제요약

입력된 값을 자릿수로 하여 이진수에서 00 이 붙어 있거나 아예 없는 모든 경우의 수에 15746을 나눈 나머지를 구하라.

설명

먼저 이 문제를 이해하고 규칙을 찾는건 크게 어렵지 않다.

다음과 같이 피보나치수열을 이루고 있음을 알고 있다.

 

피보나치 하면 먼저 재귀함수가 떠 오를 것이다.

하지만 재귀함수를 이용하면,

다음과 같이 메모리 초과 혹은 런타임 에러가 발생한다.

RecursionError는 재귀를 너무 많이 하게 되면 발생하는 에러이다.

 

따라서 이 문제는 재귀함수로 푸는것은 불가능하다.

 

그러면 반복문을 사용해야한다.

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

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[] arr = new int[1000001];

		arr[1] = 1;
		arr[2] = 2;

		for (int i = 3; i < N + 1; i++) {
			arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
		}
		
		System.out.println(arr[N]);
	}

}

다음과 같이 배열을 초기화 하고 값을 저장하는 방식으로 진행하면 된다.

 

N에따른 결과를 바로 출력하기 위해 arr[0]은 비워 두었으며, 메모리 공간을 아끼고 싶다면

-1씩 붙여주면 된다.