[알고리즘 PS] 백준 2193번 이친수 자바 문제 풀이

문제

해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 DP로 해결할 수 있는 문제중 가장 쉬운편에 속한다.

하지만 n이 90까지 가능할 때 Integer의 범위를 넘게 되는데 해당 부분만 주의하면 될듯하다.

접근법

이친수가 될 수 있는 수는 다음과 같은 특징이 있다.

1. 0으로 시작하지 않을 것 ex) 0101
2. 1이 두 번 연속 등장하지 않을 것 ex) 1101

n이 작을 때는 충분히 손으로 계산할 수 있으므로 직접 계산해보면서 특징을 찾아 점화식을 도출해보자.

n = 1;
a[n] = {1}; // 1

n = 2;
a[n] = {10}; // 1

n = 3;
a[n] = {100, 101} // 2

n = 4;
a[n] = {1000, 1010, 1001} // 3;

...

이 문제는 2가지 경우를 찾아야 한다.

• 0이 올 수 있는 경우
• 1이 올 수 있는 경우

0이 올 수 있는 경우
우선 n이 이친수가 되려면 n-1번쨰 에서 0을 붙히면 무조건 해당 수는 이친수가 된다.

 

1이 올 수 있는 경우
이제 1이 올 수 있는 경우를 찾아야 하는데, n보다 작은 수에 1을 바로 붙일 수 없다.

왜냐? 만약 1이 혼자 왔다가 앞선 수가 1이라면 11이 되므로 이친수에 해당하지 않는다.

그래서 1이 오기 위해서는 01이 와야 한다.

그럼 01이라는 수가 붙으려면 n-2 번째 수에서 붙어야 하므로 n-2번째와 n-1번쨰 수를 더해주면 된다.

오답 후보

이번 문제의 정답률은 30퍼센트이다.

아마 이번 문제에서 많이 틀렸을 이유가 n이 계속 증가하다 Integer의 범위보다 더 큰 수를 저장해야할 때 정수 오버플로우가 발생한다.

그래서 출력 자료형을 long으로 변경해야 한다.

정답 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[91]; // n 자리의 이친수 갯수
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        dp[3] = 2;

        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        bw.write(String.valueOf(dp[n]));
        bw.flush();
        bw.close();
    }
}

---

문제 회고

문제를 풀 때 처음부터 무턱대고 들어가는 습관은 조금 신경쓰기 시작했다.
만약 이번 문제도 어떻게 해결할지 알았다고 해서 무턱대고 들어갔더라면, long 자료형을 써야한다는 것도 모르고 한 번에 통과하기는 힘들었을 것이다.
해당 문제는 작년 교내 소프트웨어 경진 대회에서 만났던 문제인데, 결국 풀지 못했던 기억이 있다.
그 때 당시에는 와.. 이건 천재만 풀어 하는 문제였는데 DP를 알고 보니 정말 간단한 문제였다는 것에 조금 허무하다 ㅎㅎ..

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.