~20년 1월 목표

Thu, 05 Dec 2019 00:00:00 +0900

이룰 것

BOJ 랭킹 500등 Discord Bot 프로젝트 Tensorflow를 이용한 <목표 관리, 예측 시스템>(가칭) 프로젝트 다익스트라 같은 알고리즘 공부하기

지금 해야할 것

하루에 BOJ 문제 1개씩 풀기 DP,탐색문제 푼것도 다시 풀어보기 Tensorflow 익히기 1일 1커밋

백준 1788번 피보나치 수의 확장 풀이

Sun, 21 Apr 2019 00:00:00 +0900

문제 풀이 방법

이 문제는 $F(n)$을 1000000000으로 나눈 나머지를 출력하면 되는 문제이기 때문에, 문자열로 할 필요없이 그냥 for문으로 해결할 수 있는 문제이다.

간단하게 for문 2개로 음수일때, 음수가 아닐때를 따져보면서 풀어보면 된다.

피보나치 수열 점화식

$n$이 음수일때의 피보나치 수열의 점화식은 $F(n) = F(n-2) - F(n-1)$으로 점화식을 새울 수 있다.

그래서 for문으로 다음과 같이 작성할 수 있다.

 for (int i = 2; i <= abs(n); i++) {
			a[i] = a[i - 2] - a[i - 1];
			a[i] %= 1000000000;//long long 범위를 넘는 것을 방지하기 위해 처음부터 1000000000으로 나눔 
}

$n$이 자연수일때는 $F(n) = F(n-1) + F(n-2)$으로 점화식을 새울 수 있다.

이 또한 for문으로 다음과 같이 작성할 수 있다.

 for (int i = 2; i <= n; i++) {
			a[i] = a[i - 1] + a[i - 2];
			a[i] %= 1000000000;//long long 범위를 넘는 것을 방지하기 위해 처음부터 1000000000으로 나눔 
}

코드

C

#include <stdio.h>
#include <math.h>
using namespace std;
long long a[1000001], n;
int main() {
	scanf("%d",&n);
	a[0] = 0;
	a[1] = 1;
	if (n < 0) {
		for (int i = 2; i <= abs(n); i++) {
			a[i] = a[i - 2] - a[i - 1];
			a[i] %= 1000000000;
		}
		if (a[abs(n)]<0)printf("-1\n");
## 		else printf("1\n");
		printf("%lld",abs(a[abs(n)]) % 1000000000);
	}
	else if (n > 0) {
		for (int i = 2; i <= n; i++) {
			a[i] = a[i - 1] + a[i - 2];
			a[i] %= 1000000000;
		}
		printf("%lld",a[n] % 1000000000);
	}
	else printf("0\n0");

	return 0;
}

C++

#include <iostream>
#include <math.h>
using namespace std;
long long a[1000001], n;
int main() {
	cin >> n;
	a[0] = 0;
	a[1] = 1;
	if (n < 0) {
		for (int i = 2; i <= abs(n); i++) {
			a[i] = a[i - 2] - a[i - 1];
			a[i] %= 1000000000;
		}
		if (a[abs(n)]<0)cout << "-1" << "\n";
		else cout << "1" << "\n";
		cout << abs(a[abs(n)]) % 1000000000;
	}
	else if (n > 0) {
		for (int i = 2; i <= n; i++) {
			a[i] = a[i - 1] + a[i - 2];
			a[i] %= 1000000000;
		}
		cout << "1" << "\n" << a[n] % 1000000000;
	}
	else cout << "0" << "\n" << "0";

	return 0;
}

다른 언어

다른 언어도 음수일때, 양수일때를 나눠 가며 각각 $F(n) = F(n-2) - F(n-1)$, $F(n) = F(n-1) + F(n-2)$ 점화식에 맞게 풀면 된다.

개발 블로그