Codetesing의 코딩공부

DP라 써놨지만 DFS로 풀었다.

DP의 규칙을 찾지 못해서 DFS로 풀어봤는데 풀렸다.

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

using namespace std;

int out = 9, n, num;

void DFS(int cnt, int cur)
{
    if (cnt > 8)
        return;

    if (cur == num)
    {
        out = min(cnt, out);
        return;
    }

    int temp = 0;
    for (int i = 0; i + cnt < 9; i++)
    {
        temp = temp * 10 + n;
        DFS(cnt + 1 + i, cur + temp);
        DFS(cnt + 1 + i, cur - temp);
        DFS(cnt + 1 + i, cur * temp);
        DFS(cnt + 1 + i, cur / temp);
    }
}

int solution(int N, int number) {
    int answer = 0;
    n = N; num = number;

    DFS(0, 0);

    answer = out;

    if (answer > 8)
        answer = -1;

    return answer;
}

백트래킹으로 유명한 N Queen 문제이다.

풀어봤던것으로 쉽게 풀었다.

#include <string>
#include <vector>

using namespace std;

bool visited[12][12] = { false, };
int out = 0, N;

bool check(int row, int column)
{
    for (int i = 0; i < N; i++)
        if (visited[row][i] == true)
            return false;

    for (int i = 0; i < N; i++)
        if (visited[i][column] == true)
            return false;

    for (int i = row, j = column; i >= 0 && j < N; i--, j++)
        if (visited[i][j] == true)
            return false;

    for (int i = row, j = column; i < N && j < N; i++, j++)
        if (visited[i][j] == true)
            return false;

    for (int i = row, j = column; i >= 0 && j >= 0; i--, j--)
        if (visited[i][j] == true)
            return false;

    for (int i = row, j = column; i < N && j >= 0; i++, j--)
        if (visited[i][j] == true)
            return false;

    return true;
}

void dfs(int row, int column, int queen)
{
    if (queen == N)
    {
        out++;
        return;
    }

    for (int j = 0; j < N; j++)
    {
        if (check(row, j))
        {
            visited[row][j] = true;
            dfs(row + 1, j, queen + 1);
            visited[row][j] = false;
        }
    }
}

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

    dfs(0, 0, 0);

    answer = out;

    return answer;
}

유명한 하노이 문제이다.

재귀로 푸는게 일반적인 방법인것 같다.

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> hanoi;

void Hanoi(int start, int end, int n) {
    if (n == 1) 
    {
        hanoi.push_back({ start, end });
        return;
    }

    Hanoi(start, 6 - start - end, n - 1);
    hanoi.push_back({ start, end });
    Hanoi(6 - start - end, end, n - 1);
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;

    Hanoi(1, 3, n);
    
    answer = hanoi;

    return answer;
}

기본적인 순열과 조합문제이다.

몫과 나머지, 순열에 따라 순서가 정해진다.

#include <string>
#include <vector>

using namespace std;

long long facto(long long num) {

    long long n = 1;

    for (int i = 2; i <= num; i++)
        n *= i;

    return n;
}

vector<int> solution(int n, long long k) {
    vector<int> answer, vt;
    for (int i = 1; i <= n; i++)
        vt.push_back(i);

    if (k == 1)
        return vt;

    k--;
    long long pre = facto(n);
    long long mod, div;

    while (vt.size() != 1) {
        pre /= n;
        mod = k % pre;
        div = k / pre;

        answer.push_back(vt[div]);
        vt.erase(vt.begin() + div);

        k = mod;
        n--;
    }
    answer.push_back(vt[0]);

    return answer;
}

간단한 문제였다. 왜 LV2 인지 잘 모르겠음.

#include <string>
#include <vector>

using namespace std;

int check(int n) {

    if (n == 1)
        return 0;

    for (int i = 2; i * i <= n; i++)
        if (n % i == 0 && n / i <= 10000000)
            return n / i;

    return 1;
}

vector<int> solution(long long begin, long long end) {
    vector<int> answer;

    for (int i = begin; i <= end; i++)
        answer.push_back(check(i));

    if (begin == 1) answer[0] = 0;
    return answer;
}