[Week 1] BOJ #1003 self review - Sososoy

[Sososoy]

BOJ #1003 self review

• 파일명: <AlgorithmReview/BOJ_1003>
• 수행시간: <4ms>

1. 문제 해결 과정

음~ 모르겠는데~ 일단 다짜고짜 0부터 6까지 써보니 규칙이 보여 피보나치처럼 재귀함수 응용하면 되겠다 했다.
근데 그 다음을 몰라서 풀이를 보니 동적 프로그래밍으로 한다고 했다.

2. 아이디어

동적 프로그래밍으로 배열마다 값을 저장하고 잘 재활용하기.
동적 배열 초기값을 조건대로 바로 설정하기.
n이 0일때와 같이 규칙에 해당하지 않는 부분은 과감히 출력문으로 그대로 써도 된다니.
n 범위 고려해서 반복문의 조건 잘 설정하기.

3. 코드 설명

'''cpp'''
#include
#include
using namespace std;

int main() {
int n, t= 0;
int memo[41] = {0, 1};

for (int n = 2; n <= 40; n++)
	memo[n] = memo[n - 1] + memo[n - 2];

cin >> t;

for (int i = 0; i < t; i++) {
	cin >> n;
	if (n == 0)
		cout << "1 0" << endl;
	else
		cout << memo[n-1] << " " << memo[n] << endl;
}

}

동적 배열을 반복문으로 돌려서 값 다 저장한다.
0의 횟수는 memo[n-1], 1의 횟수는 memo[n]에 해당함을 알고 출력한다.