[백준(BOJ)] 2193번 이친수 C++
문제 : https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
어떤 문제인가?
이친수라는 문제에서 정의된 이진수들이 있다.
n이 입력됐을 때 n자리 이친수의 개수를 출력하면 된다.
접근 방법
일단 문제가 dp(다이나믹 프로그래밍)이라는 것은 문제를 읽으면 알 수 있다.
그러므로 점화식을 세워야한다.
n = 1일 때
1
1개
n = 2일 때
10
1개
n = 3일 때
101
100
2개
n = 4일 때
1001
1010
1000
3개
.
.
.
규칙을 확인해보면 피보나치수열과 동일한 것을 알 수 있다.
dp[ i ] = dp[ i -1 ] + dp[ i - 2]
long long dp[91];n이 90까지 입력될 수 있으니 크기 91의 long long형 배열을 선언해준다.
dp[1] = 1;
dp[2] = 1;dp[1]과 dp[2]는 알 고 있으므로 1로 초기화해준다.
int n;
cin >> n;문제에서 주어진 변수인 n을 선언하고 입력받는다.
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}3부터 n까지의 dp값을 계산해준다.
cout << dp[n];dp의 n번째 인덱스 값을 출력해주면 끝!
무엇이 어려웠는가?
처음엔 dp배열을 int형으로 하여 문제를 풀고 당연히 맞다고 생각하여 바로 제출했다.
그랬더니 틀렸습니다가 떴다.
무엇이 잘못됐는지 이상해하다가 알았다.
n이 90까지 입력될 수 있는데 그렇게되면 int가 표현할 수 있는 범위를 넘어서 틀렸다고 뜬 것이다.
long long형으로 바꿔주니 성공!
배운 점
간단한 문제라도 예외가 있을 수 있으니 한 번 더 생각해보자.
굉장히 사소한 부분에서도 오류가 발생한다!