세하누나 질문답변

[ghdcksgml1]

02_1010_다리놓기

#include<iostream>

using namespace std;

long memo[30]; 

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

    int T; cin >> T;
    int N, M;

    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        memo[0] = 1; // nCn = 1
        if (N == M) { cout << memo[0] << '\n'; } 
        else {
            for (int i = 1; i <= M - N; i++) {
                memo[i] = ((N + i) * memo[i - 1]) / i; // 수정한부분
            }
            cout << memo[M - N] << '\n';
        }
    }
}

일단 bottom 방식으로 쌓아올라가는 점화식 아주 Good!!

답도 거의 맞았는데, double을 쓰면 안되는이유가 double에는 오차값이 존재해서 이 오차값들이 쌓이다보면

어떤 특수한 케이스에서 +-1 정도 답이랑 다른경우가 있어.

그래서 double을 없애고 분배법칙으로 곱한결과에 i를 나누도록 수정하면 답이 제대로 나옵니당

03_11726_2xn 타일링

#include<iostream>

using namespace std;

long long memo[1001];

int main() {
	int n; cin >> n;
	memo[1] = 1; memo[2] = 2;
	for (int i = 3; i <= n; i++) {
		memo[i] = (memo[i - 1] + memo[i - 2])%10'007; // 수정한부분
	}
	cout << memo[n] % 10'007;
}

이것도 다 맞았는데 %10007을 바텀업을 하면서 계속해줘야해

그 이유는 숫자가 기하급수적으로 커져서 memo[1000]의 값이 long long 타입의 커버가능한 범위인 2₆₃을 넘어갈 수 있어

그렇게 되면 -131232131 이런식으로 값이 저장되는데 그값의 나머지 값이랑 정답이랑은 다르게되는거야!

04_1463_1로 만들기

이 코드는 그리디 느낌으로 접근했는데 그리디로는 풀수 없는 문제야... ㅎㅎ

다이나믹 프로그래밍을 사용해야하는데 스터디때 설명해드릴게연