[Week 4] TILING2 self review - yujungee

[yujungee]

TILING2 self review

• 파일명: TILING2/yujungee.cpp
• 수행시간: 0ms

1. 문제 해결 과정

먼저 dp문제 해결 방법을 공부하기 위해, 교재 207p ~ 213p 부분을 정독했습니다.
위의 부분만 읽어도 이 문제를 푸는데 충분히 이해가 가고, 틀이 잡혔습니다.

문제를 풀기 전에 작은 수로 케이스를 계산해 봤는데, 피보나치 수열과 같은 모양이 나와 계산하기 수월했습니다.
출력도 모듈로 연산을 통해 간단하게 해결할 수 있었습니다.

처음 알고스팟에서 컴파일 오류가 났는데, 이유는 헤더파일을 추가하지 않았었습니다.
memory.h 혹은 string.h 파일을 추가하는 것을 잊지마세요. xcode에서는 추가하지 않아도 잘 실행돼서 간과할 뻔 했습니다.

2. 아이디어

dp로 해결하였습니다.

3. 코드 설명

헤더 부분

#include <iostream>
#include <string.h>    // 혹은 #include <memory.h>

변수 선언 부분

const int mod = 1000000007;     // mod는 상수로 선언했습니다.
int n;
int cache[101];   

tiling() 부분

int tiling(int width) {
    
    // 기저 사례 : width가 1 이하일 때
    if (width <= 1) return 1; 

    int& res = cache[width]; // res는 cache의 참조형
    if (res != -1) return res; // -1이 아니라면 계산된 값
    
    return res = (tiling(width-2) + tiling(width-1)) % mod;
}

피보나치 수열 모양인 tiling(width) = tiling(width-2) + tiling(width-1) 임을 사용했습니다.

main() 부분

int main() {

    int tc;
    cin >> tc;

    while(tc--) {
        memset(cache, -1, sizeof(cache));    // 초기화
        cin >> n;

        cout << tiling(n) << endl;
    }

    return 0;
}

[Queue-ri]

네 clang이랑 msvc는 헤더 추가 안해도 memset이 잘 돌아가죠..
알고스팟은 g++인데 g++은 헤더 인클루드가 필수라서 CTE 납니다.
정확히는 컴파일러 차이가 아니라 라이브러리 / 헤더 차이이고 다른 라이브러리 가져다 커스텀하면 결과가 다른데,
일반적인 경우의 기본 라이브러리라면 그렇습니다.