<Algorithm> 199. 이친수(BJO)

1. 2193번 이친수(BJO)

   사용 알고리즘 : DP

• 쉽게 풀었지만 원리를 이해하는데 시간이 좀 걸린 문제.. 

• 두번째 방법은 피보나치 원리에 의해 풀린 것이지 이 문제의 원리는 아닌 것 같다.

• 내가 생각한 원리는 0은 0을 하나 만들고 1은 0 하나를 만든다. 즉 이전의 0과 1개수가 현재 0개수 dp[i][0] = dp[i-1][0] + dp[i-1][1] 이다.

• 1은 0을 만들기 때문에 이전의 0 개수가 현재 1이 된다. 즉 dp[i][1] = dp[i-1][0]이다. 결과는 이 두개의 총합이 된다.

문제에 대한 접근&생각

1. 길이가 주어지고 해당하는 개수를 구함 -> DP! -> 규칙을 찾기위해 결과들을 나열함 -> 0과 1 각각 이전 두개의 합인 점화식! 
2. 결국 따로 할필요없이 총 개수가 이전 두개의 합과 같음 -> 피보나치!

코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

import java.util.Arrays; import java.util.Scanner; import java.util.stream.Stream;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         /************************          * DP를 이용해 이전 두개의          * 값이 현재값이 되는 피보나치를          * 이용하여 풀이한다.          ************************/         long ans = Stream.iterate(new long[]{0,1},arr->new long[]{arr[1],arr[0]+arr[1]})               .limit(n+1)               .mapToLong(arr->arr[0])               .max().getAsLong();         System.out.println(ans); //////// 두번째 방법                  long[][] dp = new long[n+1][2];         dp[1][0] = 0; dp[1][1] = 1;         if(n == 1) {             System.out.println(1);             return;         }         dp[2][0] = 1; dp[2][1] = 0;                  for(int i = 3; i <= n; i++) {             dp[i][0] = dp[i-2][0]+dp[i-1][0];             dp[i][1] = dp[i-2][1]+dp[i-1][1];         }         System.out.println(Arrays.stream(dp[n]).sum());         } }   Colored by Color Scripter

cs