딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/11049

#include <iostream>
#include <climits>

using namespace std;

int N;
int d[503];
int matrix[503][2];
long long dp[503][503];

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

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> matrix[i][0] >> matrix[i][1];
        d[i] = matrix[i][1];
    }

    d[0] = matrix[1][0];
    for (int diagonal = 1; diagonal <= N - 1; diagonal++) {
        for (int i = 1; i <= N - diagonal; i++) {
            int j = i + diagonal;
            dp[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d[i - 1] * d[j] * d[k]);
            }
        }
    }

    cout << dp[1][N] << '\n';
    return 0;
}

https://www.acmicpc.net/problem/11585

#include <iostream>

using namespace std;

#define MX 1'000'003

int N;
char arr1[2 * MX], arr2[MX];

int fail[MX];

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void getFail() {
    int j = 0;
    for (int i = 1; i < N; i++) {
        while (j > 0 && arr2[i] != arr2[j]) {
            j = fail[j - 1];
        }
        if (arr2[i] == arr2[j]) {
            fail[i] = ++j;
        }
    }
}

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


    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr1[i];
        arr1[i + N] = arr1[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> arr2[i];
    }


    getFail();

    int cnt = 0;
    int j = 0;
    for (int i = 0; i < 2 * N; i++) {
        while (j > 0 && arr1[i] != arr2[j]) {
            j = fail[j - 1];
        }

        if (arr1[i] == arr2[j]) {
            if (j == N - 1) {
                if (i - j < N)cnt++;

                j = fail[j];
            } else {
                j++;
            }
        }
    }

    int _gcd = gcd(N, cnt);
    cout << cnt / _gcd << '/' << N / _gcd << '\n';
}

https://www.acmicpc.net/problem/1701

1. 문제설명

주어진 문자열 중에 두번이상 나오는 부분 문자열의 최대 길이를 구해야한다.

하나의 문자열에서 두번 이상 나오는 부분 문자열은

KMP알고리즘에서 prefix와 suffix를 비교하는 fail함수를 만드는 과정에서 구할 수 있다.

단 이때 이 문제에서 나올 수 있는 모든 prefix의 경우를 살펴야하기 때문에

for문을 한번 돌면서 시작지점을 정하고 그때마다 kmp fail함수를 만들어서 

가장 길게 매칭되는 prefix suffix의 길이를 구해야 한다.

2. 문제풀이코드

#include <iostream>

using namespace std;

int fail[5003];

int getFail(const string &s, int start) {
    int ans = 0;

    for(int i=0; i <5003; i++){
        fail[i] = 0;
    }

    int j = 0;
    for (int i = 1; i < s.length(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = fail[j - 1];
        }

        if (s[i] == s[j]) {
            fail[i] = ++j;
            ans = max(ans, j);
        }
    }
    
    return ans;
}


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

    string s;
    cin >> s;

    int ans = 0;

    for (int i = 0; i < s.length(); i++) {
        ans = max(ans, getFail(s.substr(i,s.length()-i), i));
    }
    cout << ans << '\n';

}

https://www.acmicpc.net/problem/10266

여러 개의 각도를 지닌 두개의 시계를 비교할 때

회전하였을 때 둘이 같아질 수 있는지 비교해야 문제를 해결할 수 있다.

시계의 각도가 360,000개 있기 때문에

이를 회전하면서 비교하는 방법을 찾는 것이 중요하다.

직접 큐를 만들어서 회전하면서 for문을 돌며 비교할 경우에는 36만 * 36만 번 연산해야 하기 때문에

문제를 해결할 수 없다.

대신 비교할 text를 두번 반복해서 두고 pattern을 그에대해 비교하면

회전을 하지 않고 회전한 효과를 얻을 수 있다.

문제풀이코드 C++

#include <iostream>

#define MAX_LEN 360'000
using namespace std;

int N;
bool text[MAX_LEN * 2], pattern[MAX_LEN];
int fail[MAX_LEN];

void getFail() {
    int j = 0;

    for (int i = 1; i < MAX_LEN; i++) {
        while (j > 0 && pattern[j] != pattern[i]) {
            j = fail[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            fail[i] = ++j;
        }
    }
}


bool kmp() {
    int j = 0;
    for (int i = 0; i < 2 * MAX_LEN; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (text[i] == pattern[j]) {
            if (j == MAX_LEN - 1) {
                return true;
            } else {
                j++;
            }
        }
    }
    return false;
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        text[tmp] = 1;
        text[MAX_LEN + tmp] = 1;
    }

    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        pattern[tmp] = 1;
    }

    getFail();

    if (kmp()) {
        cout << "possible" << '\n';
    } else {
        cout << "impossible" << '\n';
    }
}

#include <iostream>
using namespace std;
#define MX 101

int n, d[MX], dp[MX][MX], P[MX][MX];

void order(int i, int j){
    if(i==j){
        cout << "M" << i;
    }
    else{
        int k = P[i][j];
        cout << "(";
        order(i, k);
        order(k+1, j);
        cout << ")";
    }

}

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> n;
        for(int i=0; i<=n; i++){
            cin >> d[i];
        }

        for(int diagonal=1; diagonal<=n-1; diagonal++){
            for(int i=1; i<=n-diagonal; i++){
                int j = i + diagonal;

                int minValue = 2e9;

                for(int k = i; k <j; k++){
                    int cur = dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j];
                    if(minValue > cur){
                        P[i][j] = k;
                        minValue = cur;
                    }
                }
                dp[i][j] = minValue;
            }
        }
        order(1, n);
        cout << '\n';
        cout << dp[1][n] << '\n';
    }
    return 0;
}

https://www.acmicpc.net/problem/2618

#include <bits/stdc++.h>

using namespace std;

const int MX = 1'000'001;
int N, W, dp[1003][1003];

vector<pair<int, int> > work;

int lastMax = MX;
pair<int, int> lastWork;

int getMaxDistance(int A, int B) {
    if (A == W || B == W) {
        return 0;
    }
    int &ret = dp[A][B];
    if (ret != -1) return ret;

    ret = MX;
    int nextWork = max(A, B) + 1;

    int ret1 = -1, ret2 = -1;
    //다음 일을 A가 할 때
    if (A == 0) {
        ret1 = getMaxDistance(nextWork, B) + abs(1 - work[nextWork].first) + abs(1 - work[nextWork].second);
    } else {
        ret1 = getMaxDistance(nextWork, B)
               + abs(work[A].first - work[nextWork].first) + abs(work[A].second - work[nextWork].second);
    }

    //다음 일을 B가 할 때
    if (B == 0) {
        ret2 = getMaxDistance(A, nextWork) + abs(N - work[nextWork].first) + abs(N - work[nextWork].second);
    } else
        ret2 = getMaxDistance(A, nextWork)
               + abs(work[B].first - work[nextWork].first) + abs(work[B].second - work[nextWork].second);

    return ret = min(ret1, ret2);
}


void reconstruct(int A, int B) {
    if (A == W || B == W) return;

    int nextWork = max(A, B) + 1;
    int ret1 = -1, ret2 = -1;
    //다음 일을 A가 할 때
    if (A == 0) {
        ret1 = dp[nextWork][B] + abs(1 - work[nextWork].first) + abs(1 - work[nextWork].second);
    } else {
        ret1 = dp[nextWork][B]
               + abs(work[A].first - work[nextWork].first) + abs(work[A].second - work[nextWork].second);
    }

    //다음 일을 B가 할 때
    if (B == 0) {
        ret2 = dp[A][nextWork] + abs(N - work[nextWork].first) + abs(N - work[nextWork].second);
    } else
        ret2 = dp[A][nextWork]
               + abs(work[B].first - work[nextWork].first) + abs(work[B].second - work[nextWork].second);

    if (ret1 < ret2) {
        cout << 1 << '\n';
        reconstruct(nextWork, B);
    } else {
        cout << 2 << '\n';
        reconstruct(A, nextWork);
    }
}


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

    cin >> N >> W;

    work.push_back({0, 0});
    for (int i = 0; i < W; i++) {
        int a, b;
        cin >> a >> b;
        work.push_back({a, b});
    }

    memset(dp, -1, sizeof(dp));
    cout << getMaxDistance(0, 0) << '\n';
    reconstruct(0, 0);

    return 0;
}

https://www.acmicpc.net/problem/16987

#include <bits/stdc++.h>

using namespace std;

struct Egg {
    int s, w;
};

Egg arr[8];

int N , ans;

void DFS(int cur) {
    if (cur == N) {
        int cnt = 0;
        //깨진 계란 갯수 확인하기
        for (int j = 0; j < N; j++) {
            if (arr[j].s <= 0) cnt++;
            ans = max(ans, cnt);
        }
        return;
    }

    for (int i = 0; i < N; i++) {
        if(i==cur) continue;
        //단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
        if (arr[cur].s <= 0 || arr[i].s <= 0){
            DFS(cur+1);
            continue;
        }
        //손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다.
        arr[i].s -= arr[cur].w;
        arr[cur].s -= arr[i].w;
        DFS(cur+1);
        arr[i].s += arr[cur].w;
        arr[cur].s += arr[i].w;
    }
}

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

    cin >> N;
    for (int i = 0; i < N; i++) {
        int s, w;
        cin >> s >> w;
        arr[i] = {s, w};
    }


    DFS(0);

    cout << ans << '\n';

    return 0;
}

https://www.acmicpc.net/problem/1941

1. 문제설명

25명의 학생 중 7명을 뽑아보는 백트래킹을 진행하면서

7명 중 4명이상이 S인지 확인하고,

7명이 모두 인접해있는지 BFS 탐색을 해서

옳으면 경우의 수를 추가해주면 된다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int ans = 0;
string arr[5];
bool student[25];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool check() {
    int num = 0;
    int x, y;
    
    for (int i = 0; i < 25; i++) {
        if (student[i]) {
            int row = i / 5;
            int col = i % 5;

            if (arr[row][col] == 'S') {
                num++;
                x = row;
                y = col;
            }

        }
    }
    if (num < 4) return false;
    
    queue<pair<int, int> > Q;
    Q.push({x, y});
    int cnt = 1;

    bool vis[5][5] = {0};
    vis[x][y] = 1;

    while (!Q.empty()) {
        int curx = Q.front().first;
        int cury = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5)continue;
            if (vis[nx][ny]) continue;
            if (!student[nx * 5 + ny]) continue;

            vis[nx][ny] = 1;
            Q.push({nx, ny});
            cnt++;
        }
    }


    return cnt == 7;
}


void DFS(int idx, int num) {
    if (num == 7) {
        if (check()) {
            ans++;
        }
        return;
    }

    for (int i = idx; i < 25; i++) {
        student[i] = 1;
        DFS(i + 1, num + 1);
        student[i] = 0;
    }
}

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

    for (int i = 0; i < 5; i++) {
        cin >> arr[i];
    }

    DFS(0, 0);
    cout << ans << '\n';

    return 0;
}