[BaekJoon/백준] 1904번 | 복습 1회 완료

타일 문제.

 

처음엔 이걸 순열과 조합으로 풀려고 시도했다.

팩토리얼을 자주 쓰게 되니 팩토리얼 값이 중복이 생기므로 메모이제이션을 활용하면 되겠다고 생각했다.

 

 

극복하지 못한 내 소스코드

#include <stdio.h>


long long fac_num[1000000];

long long factorial(int num) {
    if(num < 2)
        return fac_num[1];
    else {
        if((fac_num[num]))
            return fac_num[num];
        else
            return (fac_num[num] = num * factorial(num - 1));
    }
}

int main() {
    int n, max, i = 1, count = 0;
    scanf("%d", &n);

    fac_num[1]=1;

    max = n/2; // 최대 0 묶음 갯수

    count++; // 모두 1
    
    if(n%2==0) { // 모두 0
        count++; max--;
    }
    while(max) {
        count += factorial(n - max)/(factorial(max)*factorial(n - 2*max));
        max--;
    }
    printf("%d", count);
}

낮은 값에서 결과는 잘 뱉어내나, N = 100 정도부터 팩토리얼 값이 더 이상 담을 수 없이 커지면서 계산값을 담아낼 변수를 마련할 수가 없었다.

 

 

이건 아니겠구나..싶었다. 다른 뾰족한 수가 있는 것 같은데 그런 방식을 창조해내는건 쉽지 않았다.

 

그래서 그냥 정말 문제의 규칙을 찾아서 풀어보기로 했다.

// 1 -> 1

// 2 -> 00 11 -> 2

// 3 -> 001 100 111 -> 3

// 4 -> 0000 1111 1100 0011 1001 -> 5

// 5 -> 00000 11111 11100 11001 10011 00111 00001 10000 -> 8

 

이게 왜 이렇게 증가되는지는 모르겠지만, 피보나치의 덧셈형식으로 값이 증가되어가고 있었다.

왜 이렇게 값이 도출되는지, 어떤 규칙이 있는지까지 알면 더욱 좋겠지만, 내가 방금 그런 방식으로 접근했다가 피를 본 덕에 일단 풀기로 마음먹었다.

 

 

피보나치는 첫번째 두번째 값이 1인데, 이 경우 두번쨰 값은 2로 하여 구성해주면 된다.

 

 

 

피보형식으로 구현한 소스

참고로, 피보형식으로 구현한 것 뿐이지 피보나치 함수의 값은 아니다.

#include <iostream>
using namespace std;

long long memo[1000001];

long long fibo(int n) {
    if(memo[n]>0)
        return memo[n];
    return memo[n] = (fibo(n - 1) + fibo(n - 2)) % 15746;
}

int main() {
    int x;
    memo[1] = 1;
    memo[2] = 2;
    cin >> x;
    cout << fibo(x);
}

 

참고로, 처음에 cout << fibo(x) 부분에만  %15746을 했다가 문제가 바로 틀려버려서 또 애를 먹었다.

다른분들이 질문하신 글들을 들여다 봤는데, 리턴할때마다 저렇게 나눗셈 연산을 안해줘버리면 오버플로우가 일어난다고 하신다. 값이 초과되나보다. 그럴 것 같다.

그리고 애초부터,

문제 : "첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다" 이므로, 그를 넘는 인덱스의 값들은 모두 나눠줘서 넣어주고 그 값으로 다뤄주는게 맞기도 하다. (www.acmicpc.net/board/view/48877)

 

 

제출은 했는데 찝찝해서, 다른 분들의 제출 소스를 들여다 보았따.. 그리고 엄청난 소스를 봤다.

 

고수분의 소스

#include <bits/stdc++.h>
using namespace std;

int N, Dp[1000001] = { 0,1,2 };

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 3; i <= N; i++)
	{
		Dp[i] = Dp[i - 1] + Dp[i - 2];
		Dp[i] %= 15746;
	}
	cout << Dp[N];
}

나는 재귀함수로 구현해줬는데, 이분은 더 빠르게 포문으로 구현해주셨고 가독성도 너무 좋다.

이 코드를 보고, '아 피보나치 수열을 애초에 이렇게 포문으로 구현하는 게 더 빠르고 간결한 코드가 되겠다'는 걸 느꼈다.

나는 생각해내지못했다 ㅜ ㅠ 활용력이 아직 부족하다.

 

 

 

느낀점을 토대로 2748번 문제를 다시 봤다.

 

2748번에서 피보나치 수열을 동적계획법으로 구현했는데, 나는 이를 재귀함수로 구현했기에, 포문으로 구현하신 분의 코드를 찾아봤다.

더욱 짧고 빠르다..

 

피보나치 수열을 포문으로 구현하는 방식 Feat. 동적계획법 

(다른 분의 코드이다)

#include <stdio.h>

int main(){
    long long n,p[91]={0,1,};
    scanf("%lld",&n);
    for (int i=2;i<=n;i++) p[i]=p[i-1]+p[i-2];
    printf("%lld",p[n]);
}

---

2021.02.23 복습

다시 풀어보았다. 규칙을 찾는데, 피보나치 느낌이 보였는데 N = 6일때의 경우를 모두 구해내지를 못했다는 확신이 들어서 다른 분의 글을 보고 말았다. 두가지 경우를 찾아내지 못했고, 그 경우를 알게됨으로써 피보나치형식으로 풀 수 있었다.

#include <stdio.h>

int N;
int arr[1000001];

int main() {
    scanf("%d", &N);
    
    arr[1] = 1; arr[2] = 2;
    for(int i = 3; i <= N; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
    }
    
    printf("%d", arr[N]);
}

/*
 
 N
 1 | 1
 2 | 11 00
 3 | 100 001 111
 4 | 1100 1001 0011 0000 1111
 5 | 11111 11100 11001 10011 00111 00100 00001 10000
 6 | 111111 111100 111001 110011 100111 001111 110000 100001 000011 001100 000000 + 100100 001001 이 두개 못찾음.
 
 1 2 3 5 8 13
 */

참고 : st-lab.tistory.com/125