[Week 1] BOJ #1904 self review - yujungee

[yujungee]

BOJ #1904 self review

• 파일명: algo_2022/#1904.cpp (branch - yujungee)
• 수행시간: 32ms
• 메모리: 37056KB

1. 문제 해결 과정

처음엔 00 과 1이 등장하는지를 배열을 통해 확인해주는 방법으로 생각했다.
하지만 dp를 사용할 수 없고 시간도 오래걸려 적합하지 않다고 생각이 되었다.
풀이 블로그를 참고해서 N마다 나올 수 있는 이진 수열을 직접 세어 점화식을 구했다.
점화식을 구하고 보니 피보나치 수열을 형태였다.
그리고 이진 수열의 개수를 모두 구하고 15746로 나누어주었더니 fail이 떠서 다시 곰곰히 생각해봤다.
문제점은 피보나치 수가 매우 커질 때였다.
해결책으로, cache 배열을 long long 타입으로 설정해보았지만 여전히 실패.
상수로 15746를 두고 캐시에 미리 나눈 값으르 저장하였더니 성공하였다.

2. 아이디어

• dp, 메모이제이션, 피보나치 수열

3. 코드 설명

#include <iostream>
#include <cstring>    // memset 함수

using namespace std;
const int MOD = 15746;
int cache[1000001];

int solve(int n){
    if (n == 0 || n == 1) return cache[n]%MOD;   // 피보나치 수열 0번째와 1번째일 때 
    
    else if (cache[n] == 0) return cache[n] = (solve(n-1) + solve(n-2))%MOD;    // 아직 풀지 않은 문제일 때 피보나치 n번째 수 구하기 

    return cache[n]   // 푼 문제라면 그대로 리턴 (여기선 이미 cache의 값이 MOD로 나눠졌기 때문에 그대로 리턴하는 것이 효율적임)
}

int main(){
    int n;
    cin >> n;
    memset(cache, 0, sizeof(cache));
    cache[0] = 1;
    cache[1] = 1;
    
    cout << solve(n);
    

4. 막힌 점 및 개선 사항

dp문제를 접근할 때 반복되는 점이 안보이면 작은 수를 이용해 규칙을 찾고 점화식을 세워야겠다.
데이터의 크기를 잘 살피고 가능한 작게 만들어 저장해보자.