백준 | 11726. 2xn 타일

프로그래머스 문제로 풀기 시작

9/17

 

세로로 놓는걸 1, 가로로 2개 놓는걸 2라고 했을 때 1이랑 2 개수를 카운팅 한 다음에

그거를 중복순열로 놓고, 그 다음 1이랑 2 개수 카운팅 하고

또 중복순열로 놓고

이런식으로 하면 되지 않을까?

 

using namespace std;

int cut = 1000000007;

long long fac(int num, int end){
    long long n = 1;
    while(num>end){
        n=(n*num)%cut;
        num--;
    }
    return n;
}

int solution(int n) {
    int ans = 0;
    int one = n%2, two = n/2;
    
    while(one <= n){
        if(one == 0 || two == 0) ans++;
        else ans += (fac(one+two, one)/fac(two,1))%cut;
        one += 2;
        two = (n-one)/2;
    }
    return ans;
}

근데도 오류남. 우선 반복계산도 많고 시간도 오래 걸려서 그런 것 같음.

실행이 되는거랑 안되는게 혼재하고 있음.

#include <vector>
using namespace std;

int cut = 1000000007;

void fac(int num, vector<int> &v){
    int n = 1;
    while(n<num){
        v[n] = (v[n-1]*n)%cut;
        n++;
    }
    return;
}

int solution(int n) {
    int ans = 0;
    vector<int>v(n,1); // factorial 미리 저장하는 함수
    fac(n, v);
    
    int one = n%2, two = n/2;
    while(one <= n){
        if(one == 0 || two == 0) ans++;
        else ans += (v[one+two]/(v[one]*v[two]))%cut;
        one += 2;
        two = (n-one)/2;
    }
    return ans;
}

그래서 아예 factorial을 저장해두고 쓰는 방식으로 바꿔봤는데 이거는 실행은 되는데 답이 틀렸다고 나옴.

뭔짓을 해도 다 답이 틀렸다고만 나오고 맞는 답이 하나도 없길래 다음에 이어서 풀기로!

 

10/08

DP 문제를 풀다가 이 문제도 dp로 풀 수 있을 것 같아서 다르게 접근해봤다.

 

분명 규칙이 있을 것 같아서 조금 정리했는데

아니나 다를까 괜히 개고생했네

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int>v(n+1);
    v[1] = 1; v[2] = 2;
    for(int i = 3; i<=n; i++){
        v[i] = v[i-1] + v[i-2];
        v[i] = v[i] % 10007;
    }
    cout << v[n];
}

 

이렇게 하니까 한방에 성공~