-
2193) 이친수(pinary number) JAVA - DP백준코딩일기 2019. 12. 24. 07:38
풀이)
이친수(pinary number)
- 이친수는 0으로 시작하지 않는다.
- 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
Ex). 배열 d[N] = N자리 이친수의 개수
d[1] = 1 --------------------------------------------- 1
d[2] = 10 -------------------------------------------- 1
d[3] = 100, 101 ------------------------------------- 2
d[4] = 1000, 1001, 1010 -------------------------- 3
d[5] = 10000, 10001, 10010, 10100, 10101 ---- 5
d[6] = 100000, 100001, 100010, 100100,
101000, 101010, 100101, 101001 -------- 8규칙을 찾아보면,
d[3] = d[2] + d[1] = 1+1 = 2
d[4] = d[3] + d[2] = 2+1 = 3
d[5] = d[4] + d[3] = 3+2 = 5 이므로d[N] = d[N-1] + d[N-2] 인 것을 찾을 수 있다.
123456789101112131415161718public class Main {public static void main(String[] args) throws IOException{BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));int N = Integer.parseInt(bf.readLine());long[] d = new long[91];d[1]=1; d[2]=1;for(int i=3; i<=N; i++)d[i] = d[i-1] + d[i-2];}}http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter'백준코딩일기' 카테고리의 다른 글
1676) 팩토리얼 0의 개수 - JAVA (0) 2020.01.15 1158) 조세푸스 문제 - JAVA (0) 2020.01.06 2741) N 찍기 - JAVA (0) 2020.01.01 10814) 나이순 정렬 - JAVA (0) 2019.12.29 2751) 수 정렬하기 2 JAVA - 정렬 (0) 2019.12.26