Algorithm/ACM-ICPC

[ID: 1904] 01 타일

마산와사비 2019. 12. 31. 14:30
 

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수

www.acmicpc.net

  • 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Tile {
	private static int N;
	private static int[] d;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		d = new int[N+1];
		System.out.println(tile(N));
	}
	
	public static int tile(int n) {
		if(n == 1 || n == 2) return n;
		
		d[1] = 1;
		d[2] = 2;
		
		for(int i = 3; i <=n; i++) {
			d[i] = (d[i-1] + d[i-2])%15746;
		}
		return d[n];
	}
}

 

  • NOTE
    • n == 1 또는 n == 2 인 경우에 대해 배열에 초기화해주는 작업이 필요