백준 2193번 이친수

www.acmicpc.net/problem/2193

2193번: 이친수

IDEA

어려운 문제는 아니지만 나에게 큰 교훈을 준 문제다,,,ㅜ

문제 설명을 먼저하자면 두가지 조건을 만족시키는 0,1로만 이루어져있는 수의 개수를 구하는 거다. 

 

1. 이친수는 0으로 시작하지 않는다.

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

DP문제라고 생각해 DP로 풀었다. 

최근에 풀었던 쉬운 계단 수 문제랑 비슷해보여서 ,

DP[M][N] : 끝이 N인 길이가 M인 이친수 로 DP배열을 설정했다. 

이친수는 0으로 시작하지 않는다는 조건을 통해 DP[1][0] = 0 , DP[1][1] = 1로 초기화해주었다.

길이가 N이고 0으로 끝나는 배열은 이전의 길이가 N-1인 수 뒤에 0을 붙혀주면 된다. 

길이가 N이고 1로 끝나는 배열은 이전의 길이가 N-1이면서 0으로 끝나는 수 뒤에 1을 붙혀주면 된다

왜냐면 이친수는 1이 두번 이상 반복되면 안되기때문에 N자리가 1이라면 N-1은 무조건 0이어야한다.

 

DP[N][0] = DP[N-1][0] + DP[N-1][1] 

DP[N][1] = DP[N-1][0]

 

점화식을 이렇게 세울 수 있다. 

 

맨 처음 문제에서 주어진 조건이 N이 최대 90밖에 되지않아 자료형은 생각도 안해줬는데 틀렸다,,,,

질문 검색을 보니 이런 댓글이 있었다.

 

이런 건 대충 감으로 생각하면 안 되고, 정확하게 알아야 합니다.

"하지만 배열의 크기가 90 밖에 안되니 int도 될줄 알았는데"

배열의 크기가 얼마라는 것만으로 답이 얼마나 커질지를 예측한다는 건 불가능합니다. 그 사이에 무슨 식이 있느냐에 따라 상상할 수 없을 정도로 큰 수가 얼마든지 만들어질 수 있습니다. 한 번 90을 이 코드에 직접 넣어보세요. 어떤 수가 나오나요?

"단순히 long long은 int 보다 더 많은 수를 담을 수 있다는건 알고 있습니다."

이번 기회에 int와 long long이 정확하게 얼마나 큰 수까지 담을 수 있는지 알아보셨으면 좋겠습니다.

 

나도 이 글을 쓴 사람처럼 대충 90이니까 int겠지 ? 싶었는데 

90을 직접 넣어서 확인해보기전까지는 모르는 일이다,,, 직접 넣어보니 음수가 나오느 걸 보아 int형 범위를 벗어난다. 

✨앞으로는 최대수를 넣어서 int형 자료로 충분한지 직접 확인 후, 문제를 풀어보자!✨

 

CODE

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

long long dp[91][2];

int main() {
	int n;
	scanf("%d", &n);
	dp[1][0] = 0, dp[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}
	printf("%lld", dp[n][0] + dp[n][1]);
}