[백준 9461] 파도반 수열 (C++)

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

아이디어

문제를 풀고 다른 블로그 글들도 봤는데 규칙이 여러가지라 여러 방식의 점화식으로 풀 수 있다. 난이도가 쉬운 편의 문제이다. P(N)을 쭉 나열하면 아래와 같다.

N	P(N)
1	1
2	1
3	1
4	2
5	2
6	3
7	4
8	5
9	7
10	9
11	12
12	13

나의 경우 1~5까지는 규칙이 적용되지 않는다고 보고 P(N)=P(N-1)+P(N-5)라고 점화식을 세워서 풀었는데 P(N)=P(N-2)+P(N-3)이라고 점화식을 세울 수도 있다.

 

배운 점

1. long long 형 사용하기

코드는 그냥 재귀함수로 풀어버리면 시간초과가 나기 때문에 동적계획법을 이용해서 문제를 풀어야 한다. 또 P(100)의 경우 숫자가 굉장히 크기 때문에(888855064897) int형이 아닌 long long형에 값을 담아줘야 한다. 피보나치 수열과 비슷한 방식의 문제에는 long long을 적용하는 습관을 들이는 것이 좋을 것 같다. 피보나치 수열에서도 90번째 수 부터는 int자료형이 담을 수 있는 크기를 초과한다고 한다.

 

2. memset함수

이 문제의 경우 테스트케이스가 달라진다고 해도 굳이 원래 사용하던 배열을 초기화할 필요는 없지만 문제를 풀면서 memset함수에 대해 다시 복습했다. 일반적으로 for문이나 fill_n보다 빠르기 때문에 많이 사용한다. 다만 memset의 경우 1byte값으로 초기화가 가능하기 때문에 char형이나 0으로 배열을 채우는 것만 가능하다. 그렇지 않은 경우 fill을 사용해야한다.

//memset함수 예시
#include <string.h> //또는 #include <memory.h>
memset([배열이름], 넣을 값(1byte), sizeof([배열이름]))


//fill함수 예시
#include <algorithm>
int arr[10][20];
fill(&(arr[0][0]),&(arr[0][0])+10*20,1)

코드

#include <iostream>
#include <string.h>
using namespace std;

long long arr[101];

void setting() {
	memset(arr, 0, sizeof(arr));
	arr[1] = 1;
	arr[2] = 1;
	arr[3] = 1;
	arr[4] = 2;
	arr[5] = 2;
}

long long triangle(int a) {
	if (a < 6) {
		return arr[a];
	}
	else if (arr[a] == 0) {
		arr[a] = triangle(a - 1) + triangle(a - 5);
		return arr[a];
	}
	else {
		return arr[a];
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T, a;
	cin >> T;
	while (T--) {
		cin >> a;
		setting();
		cout << triangle(a) << "\n";
	}
}