[C] 백준 - 1904번: 01타일

3월 7일(화) - 동적계획법 1 (1904번)

1904번: 01타일

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 문제가 무슨 규칙인지 모르겠어서 일단 나열해봄

- N=1 인 경우 1개 (1)

- N=2 인 경우 2개 (00, 11)

- N=3 인 경우 3개 (001, 100, 111)

- N=4 인 경우 5개 (0000, 0011, 1001, 1100, 1111)

- N=5 인 경우 8개가 나오게되므로 피보나치 수열이라는 것을 알 수 있다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 아래 풀이를 제출했고, 시간초과가 발생

int arr[1000001];

int fibonacci(int N)
{
	if (N <= 2)
	{
		return N;
	}

	else if (N >= 3)
	{
		arr[N] =  (fibonacci(N - 2) + fibonacci(N - 1)) % 15746;
	}
	return arr[N];
}

int main(void)
{
	int N;
	scanf("%d", &N);

	printf("%d", fibonacci(N));

	return 0;
}

arr[1000001] 으로 선언할 이유가 없을 것 같아서 삭제 + 함수 호출도 시간걸릴 것 같아서 변경하기로 결정

메모리+시간을 고려해서 malloc으로 N크기의 arr배열을 선언한 이후

함수호출 없이 바로 arr[0] 과 arr[1]에 각각 1과 2를 넣은 이후

arr[2]부터는 반복문안에서 피보나치 방식으로 계산

-> 풀이 - 1

 

2. 풀이 - 1 을 보니, malloc 대신에 dp[1000001]으로 선언하면서 동적계획법으로 풀이해도 가능할 것 같음

-> 풀이 - 2

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int N;
	scanf("%d", &N);

	int* arr = (int*)malloc(sizeof(int) * N);
	arr[0] = 1;
	arr[1] = 2;

	if (N > 2)
	{
		for (int i = 2; i < N; i++)
		{
			arr[i] = (arr[i - 2] + arr[i - 1]) % 15746;
		}
	}

	printf("%d", arr[N-1]);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int N;
	scanf("%d", &N);

	int dp[1000001];
	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= N; i++)
	{
		dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
	}

	printf("%d", dp[N]);
	return (0);
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ