C++ / 백준 / 2193 / 이친수

문제

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

2193번: 이친수

문제풀이

N이 90까지니까 개수가 별로 안 크겠지라고 생각하고 int형 배열을 사용했다가 틀리고 long long형으로 고치고 맞았다.

DP문제는 웬만하면 long long형을 쓰는 게 나을 것 같다.

 

이 문제에는 규칙이 있다.

1. 첫 번째 숫자는 무조건 1로 시작한다.

2. 1로 연속된 숫자는 불가능하다.

1, 2번을 합치면 모든 이친 수는 10으로 시작한다는 것을 알 수 있다.

 

ex) 5자리 숫자일 때, 10을 제외하면 3자리 숫자가 남는다.

0으로 시작하는 수는 없지만 편의상 DP[0]=1로 둔다.

 

세 자릿수 첫 번째 자리에 1이 들어가는 경우 -> DP[3]

세 자릿수 첫 번째 자리에 0이 들어가는 경우

   · 세 자릿수 두 번째 자리에 1이 들어가는 경우 -> DP[2]

   · 세 자릿수 두 번째 자리에 0이 들어가는 경우

        · · 세 자릿수 세 번째 자리에 1이 들어가는 경우 -> DP[1]

        · · 세 자릿수 세 번째 자리에 0이 들어가는 경우 -> DP[0]

따라서 DP[5] = DP[3]+DP[2]+DP[1]+DP[0]이다.

 

DP[n]는 DP[0]~DP[n-2]을 모두 더한 값이다.

 

코드

#include <iostream>
using namespace std;

int main() {
	int N = 0;
	cin >> N;
	long long DP[91] = { 0, };
	DP[0] = DP[1] = DP[2] = 1;

	for (int i = 3; i <= N; ++i) {
		for (int j = 0; j <= i - 2; ++j) {
			DP[i] += DP[j];
		}
	}		
	cout << DP[N];
}