[java 백준] 실버3/2193번 이친수

https://www.acmicpc.net/problem/2193

2193번: 이친수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static int n;
    public static long[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
        dp = new long[n + 1][2];
        dp[1][1] = 1;
        dp[1][0] = 0;
 
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 2; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] + dp[i - 1][1];
                } else {
                    dp[i][j] = dp[i - 1][0];
                }
            }
 
        }
        long count = 0;
        for (int j = 0; j < 2; j++) {
            count += dp[n][j];
 
        }
        System.out.println(count);
 
    }
 
}

 

이 문제는 다른 dp 문제들 처럼 합하는게 중요한 문제였는데, 어떻게 합하는가가 핵심인 문제였다.

2차원 배열 dp를 만들어준다. dp[1][0]=0의 의미는 1의 경우 한자리 즉, 자리수를 의미하고 0은 그 정수의 맨 끝에 있는 수가 0이라는 것을 의미한다. 

한 자리수인 이친수는 1 밖에 없고 0으로 끝나지 않으므로 dp[1][0]=0이다.

이런 방식으로 n까지 구해나가면 된다. 

 

풀면서 잘못 생각한 부분

---

 

나는 규칙을 잘못 생각했다.  처음 생각해낸 코드는

if(dp[i-1][0]>=1){
   dp[i][0]=dp[i-1][0]+1;
   dp[i][1]=dp[i-1][0]+1;
}
if (dp[i-1][1]>=1){
   dp[i][0]=dp[i-1][1]+1;
   dp[i][1]=dp[i-1][0];
}