[백준, 2193번] 이친수 (다이나믹 프로그래밍 : DP, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 이친수" 문제는 아래의 조건을 만족하는 수를 이친수라고 할 때 입력되는 N 자리수의 이친수 개수를 구하는 문제입니다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

---

 

즉, 위와 같이 0으로 시작하지 않고, 11을 부분 문자열로 가지지 않는 수를 구하면 되는 문제입니다.

 

이 문제의 조건을 자세히 살펴보면 2가지 핵심 요구사항이 있습니다.

1. 0으로 시작할 수 없다
2. 1이 연속으로 나타날 수 없다 (11을 부분 문자열로 가질 수 없다)

이러한 조건을 바탕으로 이친수를 단계적으로 만들어보겠습니다.

 

1 자리 이친수

 

먼저 1자리 이친수는 "1"밖에 없습니다 (0으로 시작할 수 없으므로).

 

2 자리 이친수

 

2자리 이친수를 만들려면, 1 뒤에는 1이 올 수 없으므로(조건 2) 0만 올 수 있습니다. 따라서 2자리 이친수는 "10"입니다.

 

3 자리 이친수

 

3자리 이친수를 만들 때는 2자리 이친수인 10의 끝자리가 0이므로, 그 뒤에 0이나 1 모두 올 수 있습니다. 따라서 "100"과 "101"이 가능합니다.

 

이를 통해 다음과 같은 규칙을 발견할 수 있습니다.

• 마지막 자리에 0️⃣을 추가할 때
  • 이전 숫자가 무엇으로 끝나든(0이든 1이든) 상관없이 추가 가능
• 마지막 자리에 1️⃣을 추가할 때
  • 이전 숫자가 반드시 0으로 끝나야만 추가 가능

이러한 규칙을 보면, 현재 자리수의 이친수를 구하기 위해서는 이전 자리수의 결과를 활용하고 있음을 알 수 있습니다.

 

즉, 큰 문제(N자리의 이친수)를 작은 문제(N-1자리의 이친수)로 나누어 해결할 수 있으며, 이전에 계산한 결과를 재사용하게 됩니다. 이러한 특성은 다이나믹 프로그래밍을 적용하기에 매우 적합합니다.

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

 

그러면 점화식은 다음과 같이 형성됩니다.

 

• dp[i][0] = dp[i-1][0] + dp[i-1][1]
  • 0은 어떤 수 뒤에도 올 수 있음
  • 그래서 이전 자리수에서 0으로 끝난 개수 + 1로 끝난 개수
• dp[i][1] = dp[i-1][0]
  • 1은 0 뒤에만 올 수 있음 (11이 안되므로)
  • 그래서 이전 자리수에서 0으로 끝난 개수만

---

 

 

그러면 각 자리수의 DP 배열을 구할 수 있고, 최종적으로 원한는 값인 N 자리의 이친수는 0으로 끝나는 수 + 1로 끝나는 수를 더하면 최종적 값이 됩니다.

---

전체 코드