[백준(BOJ)] 2193번 이친수 C++

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

2193번: 이친수

 

 

어떤 문제인가?

이친수라는 문제에서 정의된 이진수들이 있다.

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형으로 바꿔주니 성공!

 

 

배운 점

간단한 문제라도 예외가 있을 수 있으니 한 번 더 생각해보자.

굉장히 사소한 부분에서도 오류가 발생한다!