개요

[링크]백준 2193번: 이진수

• 입력
  첫째 줄에 N이 주어진다.

• 출력
  첫째 줄에 N자리 이친수의 개수를 출력한다.

접근 방식

• 첫번째 방식은
  1이나 0을 추가할때 이전 값이 0인지 1인지를 함수에 넣어놓고
  재귀를 이용해 구현했다.
  하지만 값 저장 하면서 이미 저장된 값이면 끊어야하는 데,
  단순 재귀로 구현을 해서 틀렸다.

  -> 이 방식을 2차원 배열 dp를 사용해 바텀-업으로 구현을 하였다.

• 두번째 방식은
  탑다운 방식을 이용한 방법인데, 인자로 총 숫자의 갯수, 맨 앞의 숫자값을
  넘겨서 사용하는 방식이다.

첫 번째 방식 코드

#include<iostream>
#include<vector>

using namespace std;
vector<int> v(91,0);
long long dp[91][2];

void input(int& amount) {
	cin >> amount;

	//초기화 
	for (int i = 1; i <= 90; i++) {
		dp[i][0] = -1;
		dp[i][1] = -1;
	}
}


void solution(int amount) {
		dp[1][0] = dp[1][1] = 1;
	for (int i = 2; i <= amount; i++) {
		dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
		dp[i][1] = dp[i - 1][0];
	}
}





int main() {
	int amount=0,Ans=0;
	input(amount);
	solution(amount);
	cout << dp[amount][1];

}

두번째 방식 코드

#include<iostream>
#include<vector>

using namespace std;
vector<int> v(91,0);
long long dp[91][2];

void input(int& amount) {
	cin >> amount;

	//초기화 
	for (int i = 1; i <= 90; i++) {
		dp[i][0] = -1;
		dp[i][1] = -1;
	}
}


long long solution(int length, int first) {
	long long& ret = dp[length][first];
	if (ret != -1) return ret;
	if (length == 1) return 1;
	if (first == 0) ret= solution(length - 1, 0) + solution(length - 1, 1);
	else ret=solution(length - 1, 0);

	return ret;

}

int main() {
	int amount=0,Ans=0;
	input(amount);

	long long ans = solution(amount, 1);
	cout << ans;
}

문풀후생

처음에 두번째 방식의 ret값에서 참조자를 사용안했더니
시간초과가 나서 뭔가하고 한참 찾고 고민을 했었다.

참조자를 사용 안 하면 dp배열에 원소값들이 저장이 안되므로 그냥 단순 재귀와 다름이 없다.

또한 찾은 사실은 전역변수처럼 cpu에 이미 저장된 주소를 참조자가 가져다 쓴다면
캐시 hit가 발생해 그냥 int a=b보다 int& a=b가 많이 불릴수록 훨씬 더 성능차이가 난다는
사실도 배웠다.

출처: [링크] 백준 질문글