Codetesing의 코딩공부

기본적인 DP문제였다.

#define DIV 1234567

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    vector<int> DP(n + 1, 0);
    DP[1] = 1;
    DP[2] = 2;

    for (int i = 3; i <= n; i++)
        DP[i] = (DP[i - 1] + DP[i - 2]) % DIV;

    answer = DP[n];

    return answer;
}

흔한 분할정복 문제며, 쿼드트리를 사용하는 문제였다.

자주 보이던 문제 유형이라 어렵진 않았다. 시키는대로 구현하면 된다.

#include <string>
#include <vector>

using namespace std;

vector<int> ans(2, 0);
vector<vector<int>> map;

void QUARD(int start_x, int start_y, int n)
{
    int find_num = map[start_x][start_y];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if (map[start_x + i][start_y + j] != find_num)
            {
                n /= 2;
                QUARD(start_x, start_y, n);
                QUARD(start_x + n, start_y, n);
                QUARD(start_x, start_y + n, n);
                QUARD(start_x + n, start_y + n, n);
                return;
            }

    ans[find_num]++;
    return;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    int n = arr.size();
    map = arr;

    QUARD(0, 0, n);

    answer = ans;

    return answer;
}

처음엔 하드코딩으로 했는데 터져서 규칙을 찾았다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    for (long long i = left; i <= right; i++)
        answer.push_back(max(i / n, i % n) + 1);

    return answer;
}

 2xn에서 변형된 문제인거같다.

비슷하게 DP로 풀었고 좀 더 경우가 많았다.

#include <string>
#include <vector>

#define MOD 1000000007

using namespace std;

int solution(int n) {
    int answer = 0;

    if (n % 2 == 1)
        return 0;

    vector<long long> DP(n + 1);
    DP[0] = 1;
    DP[2] = 3;

    for (int i = 4; i <= n; i += 2)
    {
        DP[i] = DP[i - 2] * 3;
        for (int j = i - 4; j >= 0; j -= 2)
            DP[i] += DP[j] * 2;
        DP[i] %= MOD;
    }

    answer = DP[n];

    return answer;
}

크게 어렵지 않았다. 왜 LV2 인지 모르겠음.

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;

    for (; n != 0; n /= 2)
        if (n % 2 == 1)
            ans++;

    return ans;
}