Code and Crescendo raccoon

프로그래머스 파괴되지 않은 건물 문제입니다.

문제

N x M 형태의 그래프가 주어집니다. 이때, 각 노드는 건물을 의미하고, 숫자는 방어력을 의미합니다.
방어력이 0 이하가 되면 건물은 파괴되고, 1 이상이면 건물은 생존합니다.
이때, 라운드를 거치면서 건물의 방어력을 회복하거나 공격하는 일이 벌어집니다.(건물이 파괴되어도 1 이상의 방어력으로 회복된다면 건물은 다시 생존하게 됩니다.)
라운드를 다 거친 후 생존한 건물의 개수를 출력하시오.

알고리즘 아이디어

이 코드는 GPT에 도움을 받아 작성되었습니다.

1. 한번씩 변화를 모두 업데이트를 한다면 시간초과가 난다.
2. 한번에 변화를 업데이트를 해야 한다.(업데이트 할 그래프가 너무 큼)
3. 따라서 누적합으로 접근해서 풀어내야 한다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n = board.size();
    int m = board[0].size();
    vector<vector<int>> diff(n + 1, vector<int>(m + 1, 0));
    
    for(int i = 0; i < skill.size(); i++) {
        int type = skill[i][0];
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        int degree = skill[i][5];
        if(type == 1) degree = -1 * degree;
        diff[r1][c1] += degree;
        diff[r1][c2 + 1] -= degree;
        diff[r2 + 1][c1] -= degree;
        diff[r2 + 1][c2 + 1] += degree;
    }
    
    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            diff[i][j] += diff[i][j - 1];
        }
    }
    
    for (int j = 0; j < m + 1; j++) {
        for (int i = 1; i < n + 1; i++) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            board[i][j] += diff[i][j];
            if (board[i][j] > 0) answer++;
        }
    }
    return answer;
}

프로그래머스 유연근무제 문제입니다.

문제

그렙에서는 유연 근무제를 실행할려고 합니다. 이때 직원들의 참여율을 높이기 위해서 일주일동안 지각을 안한 직원에게 상품을 줄려고 합니다. 이때, 희망 시각보다 10분정도는 늦어도 괜찮습니다.
schedules에는 직원들의 희망 출근 시간이 저장되어있고, timelogs는 직원들의 실제 출근 데이터가 저장 되어있습니다. 주말을 제외한 주중 출근을 한번도 지각하지 않은 직원의 명수를 출력해주세요.

알고리즘 아이디어

1. schedules에서 하나의 데이터를 선택한 후, 10분 뒤 시간을 저장합니다.
2. timelogs에서 데이터를 하나씩 비교하면서 정시 출근 날짜의 데이터를 얻습니다.
3. 위 데이터가 5가 아니라면, 한번이라도 지각했으므로 상품을 가져갈 수 없습니다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int endday[8][2] = {{0, 0}, {5, 6}, {4, 5}, {3, 4}, {2, 3}, {1, 2}, {0, 1}, {6, 0}};

int solution(vector<int> schedules, vector<vector<int>> timelogs, int startday) {
    int answer = 0;
    for(int i = 0; i < schedules.size(); i++) {
        int start = schedules[i];
        if(start % 100 + 10 >= 60) {
            start = start + 100 - 60 + 10;
        } else {
            start += 10;
        }
        vector<int> time = timelogs[i];
        int count = 0;
        for(int j = 0; j < 7; j++) {
            if(endday[startday][0] == j || endday[startday][1] == j) {
                continue;
            } else if(time[j] <= start) {
                count++;
            }
        }
        if(count == 5) {
            answer++;
        }
    }
    return answer;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!

프로그래머스 코딩 테스트 공부 문제입니다.

문제

코딩 테스트를 풀기 위해선는 알고력과 코딩력 2가지 능력이 필요합니다.
처음에 각 능력치가 주어지고, 문제가 주어집니다. 각 문제는 푸는데 소요되는 시간, 문제를 풀기 위한 알고력 및 코딩력, 그리고 풀어낸 후 얻는 알고력 및 코딩력이 주어집니다.
만약 문제를 풀 수 없다면, 1의 시간을 소요하여 알고력 혹은 코딩력을 1 증가시킬 수 있습니다.
모든 문제를 풀기 위한 최소의 시간을 구해 출력하시오.

알고리즘 아이디어

1. 모든 문제를 풀기 위한 최소의 알고력과 코딩력을 구한다.
2. 이 알고력과 코딩력에 도달하기 위해 필요한 모든 경로를 DP에 저장한다. (이때 값을 비교하면서 최솟값을 저장한다.)
3. 그 후, 최소의 알고력과 코딩력에 저장되어있는 시간을 출력한다.
4. 초기값에서 만약 필요한 알고력과 코딩력이 최댓값을 넘었다면, 시작점을 변경한다.

코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int max_alp = 0, max_cop = 0;
    
    for (auto& problem : problems) {
        max_alp = max(max_alp, problem[0]);
        max_cop = max(max_cop, problem[1]);
    }
    
    vector<vector<int>> dp(151, vector<int>(151, INT32_MAX));
    
    alp = min(alp, max_alp);
    cop = min(cop, max_cop);
    
    dp[alp][cop] = 0;
    
    for (int i = alp; i <= max_alp; i++) {
        for (int j = cop; j <= max_cop; j++) {
            if (i + 1 <= 150) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            } if (j + 1 <= 150) {
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
            }

            for (auto& problem : problems) {
                int req_alp = problem[0], req_cop = problem[1];
                int gain_alp = problem[2], gain_cop = problem[3], cost = problem[4];

                if (i >= req_alp && j >= req_cop) {
                    int new_alp = min(i + gain_alp, max_alp);
                    int new_cop = min(j + gain_cop, max_cop);
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost);
                }
            }
        }
    }
    
    return dp[max_alp][max_cop];
}

프로그래머스 사라지는 발판 문제입니다.

문제

플레이어 A, B가 있습니다.
각 플레이어는 시작 지점이 존재합니다.(aloc, bloc)
각 플레이어는 상하좌우 4방향으로 한칸 움직일 수 있습니다. (그러나 맵 밖으로 나갈 수 없습니다.)
한칸 움직인 순간, 자신이 있던 자리는 다시 밟을 수 없습니다. (상대 플레이어도 밟을 수 없습니다. / 경로 자체가 없어졌다고 생각해야 합니다.)
각 플레이어는 최선의 선택을 합니다.(이길 수 있으면 가장 빠르게 끝내는 방법으로 움직이고, 진다면 가장 늦게 지도록 움직입니다.)
이때, A와 B의 플레이어의 움직인 총 횟수를 출력하시오.

알고리즘 아이디어

DP로 풀었다가 너무 어려워서 GPT에 도움을 받았다...

1. 일단 최선의 선택을 한다는 것은 모든 노드를 탐색해야 한다. (완전 탐색 진행)
2. 가장 최선의 선택을 한다는 것은 DFS로 완전 탐색을 진행한 후에 A가 이겼는지, B가 이겼는지 판단한 후, 경우의 수를 세야 한다.
3. 따라서 Minimax 알고리즘을 DFS에 적용시켜야 한다.

코드

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

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

pair<bool, int> dfs(vector<vector<int>> board, int ax, int ay, int bx, int by, bool turn) {
    int x, y;
    if(turn) {
        x = ax; y = ay;
    } else {
        x = bx; y = by;
    }

    if (board[x][y] == 0) {
        return {false, 0};
    };

    bool canWin = false;
    int minTurn = INT32_MAX, maxTurn = 0;

    board[x][y] = 0;

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size()) {
            continue;
        } if (board[nx][ny] == 0) {
            continue;
        }

        if (turn) {
            pair<bool, int> temp = dfs(board, nx, ny, bx, by, !turn);
            bool win = temp.first;
            int cnt = temp.second;
            if (!win) {
                canWin = true;
                minTurn = min(minTurn, cnt + 1);
            } else {
                maxTurn = max(maxTurn, cnt + 1);
            }
        } else {
            pair<bool, int> temp = dfs(board, ax, ay, nx, ny, !turn);
            bool win = temp.first;
            int cnt = temp.second;
            if (!win) {
                canWin = true;
                minTurn = min(minTurn, cnt + 1);
            } else {
                maxTurn = max(maxTurn, cnt + 1);
            }
        }
    }

    board[x][y] = 1;

    if (canWin) {
        return {canWin, minTurn};
    } else {
        return {canWin, maxTurn};
    }
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    auto [win, cnt] = dfs(board, aloc[0], aloc[1], bloc[0], bloc[1], true);
    return cnt;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!

LCS 알고리즘이란?

LCS(Longest Common Substring & Longest Common Subsequence) 알고리즘은 주어진 두 문자열에서 공통된 부분의 최대 길이를 찾는 알고리즘입니다. 이 알고리즘은 동적 계획법(DP, Dynamic Programming)을 기반으로 합니다.

LCS는 두 가지 개념으로 나뉩니다:

• 최장 공통 부분 문자열 (Longest Common Substring)
• 최장 공통 부분 수열 (Longest Common Subsequence)

최장 공통 문자열(LSC, Longest Common SubString)

최장 공통 부분 문자열은 두 문자열에서 연속된 공통 문자의 최대 길이를 구하는 알고리즘입니다.

예를 들어, absedes와 adsedow라는 두 문자열이 있을 때, 최장 공통 부분 문자열은 sed입니다.

점화식

if (i == 0 || j == 0) {
    dp[i][j] = 0;
} else if (a[i] == b[j]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = 0;
}

설명

1. i == 0 || j == 0
   인덱스가 0일 경우는 비교할 문자가 없기 때문에 0으로 초기화합니다.
   (실제 구현 시 편의를 위해 dp 배열을 1-based로 구성하는 경우가 많습니다.)
2. a[i] == b[j]
   문자가 같으면, 이전까지의 공통 문자열 길이에 1을 더해줍니다.
3. a[i] != b[j]
   문자가 다르면 연속성이 끊기므로 dp[i][j] = 0으로 초기화합니다.

최장 공통 부분 수열(Longest Common Subsequence)

최장 공통 부분 수열은 연속되지 않아도 되는 공통된 문자의 최대 길이를 찾는 알고리즘입니다.

예를 들어, absedes와 adsedow라는 두 문자열이 있을 때, 최장 공통 부분 수열은 ased입니다.

점화식

if (i == 0 || j == 0) {
    dp[i][j] = 0;
} else if (a[i] == b[j]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

설명

1. i == 0 || j == 0
   비교할 문자가 없기 때문에 0으로 초기화합니다.
2. a[i] == b[j]
   문자가 같으면, 해당 문자를 포함해 이전 값에서 +1을 더합니다.
3. a[i] != b[j]
   문자가 다르면, 이전 단계 중 더 큰 값을 선택해 이어갑니다.
   (연속되지 않아도 되므로 어느 쪽에서 온 값이든 상관없습니다.)

최장 공통 부분 수열 찾기

지금까지는 최장 공통 부분 수열의 길이만을 구하는 방식이었습니다.
이제는 실제 수열 자체를 추적해서 구해보겠습니다. 이를 위해서는 앞서 구한 dp 테이블을 기반으로 추적이 필요합니다.

역추적 코드 예시

if (a[i - 1] == b[j - 1]) {
    lcs += as[i - 1];
    i--;
    j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
    i--;
} else {
    j--;
}

설명

1. a[i - 1] == b[j - 1]
   문자가 같다면 공통 수열에 포함되므로 저장하고, 양쪽 인덱스를 줄입니다.
2. dp[i - 1][j] > dp[i][j - 1]
   왼쪽 위에서 온 값이 더 크면, 해당 방향으로 이동합니다.
3. 그 외의 경우
   위 방향(dp[i - 1][j])보다 왼쪽(dp[i][j - 1])이 더 크거나 같으므로 왼쪽으로 이동합니다.

이 과정에서 수열은 뒤집힌 순서로 저장되므로, 최종적으로 역순(reverse) 처리를 해야 올바른 수열이 됩니다.

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!

백준 9252번 문제입니다.

알고리즘 아이디어

문제에서 명시한 것처럼 이 문제는 LCS(Longest Common Subsequence)을 사용해서 풀어내야 하는 문제입니다.

1) DP 정의

• dp[i][j] = 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 LCS 길이
• 초기화: dp[i][j] = 0 (공통 부분 수열의 길이는 처음에는 0이다)

2) 점화식

• 문자가 같은 경우:
  a[i] == b[j] → dp[i][j] = dp[i-1][j-1] + 1
• 문자가 다른 경우:
  a[i] != b[j] → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

즉, 현재 문자가 같다면 이전까지의 공통 수열 길이에 1을 더해주고, 다르다면 이전 경우 중 더 긴 수열을 선택하여 저장합니다.

LCS 문자열 추적 방법

이제 dp 테이블을 바탕으로 실제 LCS 문자열을 찾아봅시다.

• 시작 위치: i = a.length, j = b.length (테이블 오른쪽 하단)
• 반복하며 추적:
  • a[i] == b[j]인 경우 → lcs에 해당 문자를 추가하고, i--, j--
  • a[i] != b[j]인 경우:
    • dp[i][j-1] > dp[i-1][j]이면 j--
    • 그렇지 않으면 i--

즉, 문자가 같으면 LCS에 추가하고, 다르다면 dp 테이블에서 더 큰 값이 나온 방향으로 이동하며 추적합니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    string as, bs;
    cin >> as >> bs;

    int n = as.size(), m = bs.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (as[i - 1] == bs[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    string lcs;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (as[i - 1] == bs[j - 1]) {
            lcs += as[i - 1];
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(lcs.begin(), lcs.end());

    cout << dp[n][m] << endl;
    if (!lcs.empty()) cout << lcs << endl;

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

백준 14002번 문제입니다.

알고리즘 아이디어

이 문제는 동적 계획법(DP) + 최장 증가 수열(LIS) 을 사용하여 해결할 수 있다.

1) DP 배열 정의

• dp[i] = i번째 수를 포함한 최대 수열의 길이
• dplist[i] = i번째 수를 포함한 수열
• 초기화:
  • dp[i] = 1 (자기 자신을 포함하고 있기 때문에 초기화는 1로 한다.)
  • dp[i].push_back(list[i]) (자기 자신은 항상 포함하고 있는다.)

2) 점화식 (Transition) 

dp[i] = dp[maxIndex] + 1
dplist[i] = dplist[maxIndex]
dplist[i].push_back(list[i])

• i를 포함하기 전 가장 긴 수열의 Index를 구한 후에, 그 값에 1을 더한다.(자기 자신이 포함되므로)
• 또한, 이에 맞게 수열도 저장한다.

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> list(n, 0);
    vector<int> dp(n, 1);
    vector<vector<int>> dplist(n);
    for(int i = 0; i < n; i++) {
        cin >> list[i];
        dplist[i].push_back(list[i]);
    }

    int index = 0, MaxCount = 1;
    for(int i = 1; i < n; i++) {
        int maxDp = 0;
        int vectorIndex = -1;
        
        for (int j = 0; j < i; j++) {
            if (list[j] < list[i] && dp[j] > maxDp) {
                maxDp = dp[j];
                vectorIndex = j;
            }
        }

        if (vectorIndex != -1) {
            dp[i] = dp[vectorIndex] + 1;
            dplist[i] = dplist[vectorIndex];
            dplist[i].push_back(list[i]);
        }

        if (dp[i] > MaxCount) {
            MaxCount = dp[i];
            index = i;
        }
    }

    cout << MaxCount << endl;
    for(int i = 0; i < dplist[index].size(); i++) {
        cout << dplist[index][i] << " ";
    }
    cout << endl;

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

백준 2096번 문제입니다.

알고리즘 아이디어

이 문제는 동적 계획법(DP) 을 사용하여 해결할 수 있다.

1) DP 배열 정의

• maxDp[i] = i번째를 선택하였을 때, 가장 큰 값
• minDp[i] = i번째를 선택하였을 때, 가장 작은 값
• 초기화:
  • maxDp[i] = 0 (0원을 만들기 위해 필요한 동전 수는 0개)
  • minDp[i] = 0 (min값이지만, 처음 데이터는 더해지므로 0으로 두어도 괜찮다.)

2) 점화식 (Transition)

temp = max(maxDp[0], maxDp[1], maxDp[2]) + b;
maxDp[1] = temp;

• 즉, 이 수를 선택할 수 있는 DP값들 중 가장 큰 값에 현재 수를 더해서 DP에 저장한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n;
    cin >> n;

    int maxDp[3] = {0}, minDp[3] = {0};

    for (int i = 0; i < n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;

        int tmpMax0 = max(maxDp[0], maxDp[1]) + a;
        int tmpMax1 = max({maxDp[0], maxDp[1], maxDp[2]}) + b;
        int tmpMax2 = max(maxDp[1], maxDp[2]) + c;

        int tmpMin0 = min(minDp[0], minDp[1]) + a;
        int tmpMin1 = min({minDp[0], minDp[1], minDp[2]}) + b;
        int tmpMin2 = min(minDp[1], minDp[2]) + c;

        maxDp[0] = tmpMax0;
        maxDp[1] = tmpMax1;
        maxDp[2] = tmpMax2;

        minDp[0] = tmpMin0;
        minDp[1] = tmpMin1;
        minDp[2] = tmpMin2;
    }

    int maxScore = max({maxDp[0], maxDp[1], maxDp[2]});
    int minScore = min({minDp[0], minDp[1], minDp[2]});

    cout << maxScore << " " << minScore << endl;
    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

백준 17070번 문제입니다.

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

알고리즘 아이디어

이 문제는 동적 계획법(DP) + 너비 우선 탐색(BFS) 을 사용하여 해결할 수 있다.

1) DP 배열 정의

• dp[x][y] = (x, y)위치에 올 수 있는 경우의 수
• 초기화:
  • dp[2][1] = 1 (시작 지점)
  • dp[x][y] = 0 (초기에는 어떤 곳도 갈 수 없다.)

2) 점화식 (Transition) 그 위치에 갈 수 있다면:

dp[x][y]++;

• 그 위치에 갈 수 있다면 경우의 수 하나를 증가시킨다.
  • 이때, 전 위치의 dp값을 그대로 더하면 안된다. 이유는 도착한 방향에 따라서 다음 위치가 결정되기에, 잘못된 답을 내놓게 된다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct moving {
    int dir;
    int x, y;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for(int y = 1; y <= n; y++) {
        for(int x = 1; x <= n; x++) {
            cin >> graph[x][y];
        }
    }

    queue<moving> q;
    q.push({0, 2, 1});
    dp[2][1] = 1;

    //  0 - 가로, 1 - 세로, 2 - 대각선
    while(!q.empty()) {
        int dir = q.front().dir;
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        if(dir == 0) {
            if(x + 1 <= n) {
                if(graph[x + 1][y] == 0) {
                    q.push({0, x + 1 , y});
                    dp[x + 1][y]++;
                }
            }
            if(x + 1 <= n && y + 1 <= n) {
                if(graph[x + 1][y + 1] == 0 && graph[x + 1][y] == 0 && graph[x][y + 1] == 0) {
                    q.push({2, x + 1 , y + 1});
                    dp[x + 1][y + 1]++;
                }
            }
        } else if(dir == 1) {
            if(y + 1 <= n) {
                if(graph[x][y + 1] == 0) {
                    q.push({1, x , y + 1});
                    dp[x][y + 1]++;
                }
            }
            if(x + 1 <= n && y + 1 <= n) {
                if(graph[x + 1][y + 1] == 0 && graph[x + 1][y] == 0 && graph[x][y + 1] == 0) {
                    q.push({2, x + 1 , y + 1});
                    dp[x + 1][y + 1]++;
                }
            }
        } else {
            if(x + 1 <= n) {
                if(graph[x + 1][y] == 0) {
                    q.push({0, x + 1 , y});
                    dp[x + 1][y]++;
                }
            }
            if(y + 1 <= n) {
                if(graph[x][y + 1] == 0) {
                    q.push({1, x , y + 1});
                    dp[x][y + 1]++;
                }
            }
            if(x + 1 <= n && y + 1 <= n) {
                if(graph[x + 1][y + 1] == 0 && graph[x + 1][y] == 0 && graph[x][y + 1] == 0) {
                    q.push({2, x + 1 , y + 1});
                    dp[x + 1][y + 1]++;
                }
            }
        }
    }

    cout << dp[n][n] << endl;

    return 0;
}

백준 2133번 문제입니다.

알고리즘 아이디어

이 문제는 동적 계획법(DP) 을 사용하여 해결할 수 있다.

1) DP 배열 정의

• dp[i] = 가로의 길이가 i일때, 경우의 수
• 초기화:
  • dp[0] = 1 (계산을 위한 편의 사항)
  • dp[2] = 3(일반 타일 3가지 경우의 수)

2) 점화식 (Transition) i의 길이일 때, 타일의 경우의 수를 계산

dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2 + ... + dp[0] * 2

• 기본 타일 구성은 다음과 같다.

이때, 길이가 4 이상이 된다면 다음과 같은 특수 타일이 나오게 된다.

• n = 4인 경우

• n = 6인 경우

이처럼 특수 타일은 길이가 짝수마다 2개씩 존재하게 된다.

따라서 점화식은 바로 직전 타일에 일반 타일 3개가 더 붙여지는 경우와 특수 타일들이 붙는 경우로 분리된다.

• 일반 타일이 붙는 경우
  • dp[i - 2] * 3
• 특수 타일이 붙는 경우
  • dp[i - 4] * 2 + dp[i - 6] * 2 + ... + dp[0] * 2
  • 이때, dp[0]가 0이면 안되므로 1로 정의한다.

코드

#include <iostream>
#include <vector>

using namespace std;

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

    int n;
    cin >> n;

    if(n % 2 != 0) {
        return 0;
    }

    vector<int> dp(n + 1, 0);
    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;
        }
    }

    cout << dp[n] << endl;

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!