[백준/C++] 2193번. 이친수

문제

2193번: 이친수

---

1. 첫 번째 풀이

사고 과정

자릿수를 인덱스로 하는 DP가 바로 떠올랐다.

 

앞선 자리의 수가 0으로 끝났다면, 0과 1 두 가지를 붙일 수 있다.

반대로 1로 끝났다면, 오직 0만 붙일 수 있다.

 

0으로 끝난 수의 개수와 1로 끝난 수의 개수가 필요했기에, 둘을 따로 나눠 두 개의 벡터를 쓰기로 했다.

 

1. 두 벡터 end0, end1을 생성, end0은 0, end1은 1로 초기화
2. end0[i] = end0[i - 1] + end1[i - 1]
   end1[i] = end0[i - 1]
3. end0[n]과 end1[n]을 더해서 출력

 

코드

#include <iostream>
#include <vector>

int main() {
	int n;
	std::cin >> n;

	std::vector<int> end0(n + 1, 0);
	std::vector<int> end1(n + 1, 1);

	for (int i = 2; i <= n; i++) {
		// 뒤에 0을 붙이는 경우의 수
		end0[i] = end0[i - 1] + end1[i - 1];
		// 뒤에 1을 붙이는 경우의 수
		end1[i] = end0[i - 1];
	}

	std::cout << end0[n] + end1[n];
}

 

결과

어째서인지 몰라도 틀렸습니다가 떴다.

---

2. 마지막 풀이

사고 과정

반례를 알아내기 위해 1부터 차례대로 계산해봤는데, 문제가 없었다.

 

그래서 90을 입력했더니, 음수 값이 나왔다. 즉 범위를 초과한 것.

 

int 범위로 커버가 안 되니 long long으로 변환했다.

 

코드

#include <iostream>
#include <vector>

int main() {
	int n;
	std::cin >> n;

	std::vector<long long> end0(n + 1, 0);
	std::vector<long long> end1(n + 1, 1);

	for (int i = 2; i <= n; i++) {
		// 뒤에 0을 붙이는 경우의 수
		end0[i] = end0[i - 1] + end1[i - 1];
		// 뒤에 1을 붙이는 경우의 수
		end1[i] = end0[i - 1];
	}

	std::cout << end0[n] + end1[n];
}

 

결과

 

다행히 이번엔 성공 했다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/18533239

parkky님의 코드. 숏코딩의 늪 사이 한 줄기 빛.

 

내 코드와 비교

이해하기 쉽게 쓰자면, end1[i - 1] = end0[i - 2]이기 때문에 end0[i] = end0[i - 1] + end0[i - 2]가 된다.

 

end0을 dp로 바꿔쓰면 dp[i] = dp[i - 1] + dp[i - 2]다.

 

어렵게 말하면, 피보나치 수열이다.

---

강평

문제는 쉽게 풀었지만, 피보나치 수열임을 깨닫지 못 했다. 이게 피보나치라니...!

 

그리고 저번 글에 이어, 또다시 변수 2개로 풀 수 있었다. DP의 성질에도 합당하니, 다음부턴 변수로 DP하는 법을 써볼까 한다.