경우없는 개발 블로그

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

#문제 해결 방법

이 문제를 해결하기 위한 로직은 '슬라이딩 윈도우' 기법을 사용합니다. 이 기법은 일정 범위의 데이터를 순차적으로 이동시키면서 연산을 수행하는 방법입니다. 구체적으로, 문제의 해결 로직은 다음과 같습니다:

1. 초기화:
   • maxVisitor: 최대 방문자 수를 저장하는 변수입니다. 이를 0으로 초기화합니다.
   • nowVisitor: 현재 윈도우(즉, 연속된 X일)의 방문자 총합을 저장하는 변수입니다.
   • count: 최대 방문자 수를 가지는 기간의 수를 카운트하는 변수입니다.
2. 첫 번째 윈도우 설정:
   • 처음 X일 동안의 방문자 수를 nowVisitor에 누적합니다.
   • 이 누적된 값이 초기 최대 방문자 수(maxVisitor)가 됩니다.
3. 슬라이딩 윈도우 이동:
   • 윈도우를 한 칸씩 오른쪽으로 이동시키며 새로운 X일 동안의 방문자 수를 계산합니다.
   • 이를 위해 윈도우의 가장 왼쪽 값을 빼고, 새로운 오른쪽 값을 더합니다.
   • 즉, nowVisitor = nowVisitor - visitors[start] + visitors[end + 1] 연산을 수행합니다.
4. 최대 방문자 수 갱신 및 카운트:
   • 이동할 때마다 nowVisitor가 현재의 maxVisitor보다 크면, maxVisitor를 nowVisitor로 업데이트하고 count를 1로 설정합니다.
   • nowVisitor가 현재 maxVisitor와 같다면, 같은 최대값을 가진 또 다른 기간이 있음을 의미하므로 count를 1 증가시킵니다.
5. 결과 출력:
   • 모든 가능한 윈도우를 검사한 후, maxVisitor가 0이면 "SAD"를 출력합니다. 이는 최대 방문자 수가 한 번도 0을 초과하지 않았음을 의미합니다.
   • maxVisitor가 0이 아니라면, maxVisitor와 count를 출력합니다.

이 로직을 따르면, 주어진 일수 N 동안의 방문자 데이터를 효율적으로 처리하여 �X일 동안의 최대 방문자 수와 그러한 기간이 몇 번 있는지를 정확하게 계산할 수 있습니다.

#전체 코드

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

typedef long long ll;

int main() {
    int N, X;
    cin >> N >> X;

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

    ll maxVisitor = 0, nowVisitor = 0;
    int count = 0;

    // 초기 윈도우 설정
    for (int i = 0; i < X; i++) {
        nowVisitor += visitors[i];
    }
    maxVisitor = nowVisitor;

    // 슬라이딩 윈도우
    for (int start = 0, end = X - 1; end < N; start++, end++) {
        if (nowVisitor > maxVisitor) {
            maxVisitor = nowVisitor;
            count = 1;
        } else if (nowVisitor == maxVisitor) {
            count++;
        }
        if (end + 1 < N) {
            nowVisitor = nowVisitor - visitors[start] + visitors[end + 1];
        }
    }

    if (maxVisitor == 0) {
        cout << "SAD" << endl;
    } else {
        cout << maxVisitor << endl << count;
    }

    return 0;
}

#문제 간단 정리

dp 를 사용해서 풀어야한다

#문제 해결 방법

문제 상황

먼저, 문제 상황을 이해해야 합니다. 여기서는 가로로 2칸, 세로로 N칸인 우리가 있고, 사자들을 배치하는 문제입니다. 조건은 다음과 같습니다:

• 사자들은 가로나 세로로 붙어 있을 수 없습니다.
• 사자를 한 마리도 배치하지 않는 경우도 포함합니다.

동적 프로그래밍 이해하기

DP는 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 이 문제에서는 'N번째 칸까지 사자를 어떻게 배치할 수 있는가'를 작은 문제로 삼습니다. 각 칸에 대해 다음과 같은 세 가지 경우를 생각해볼 수 있습니다:

1. 사자를 배치하지 않는 경우.
2. 사자를 첫 번째 칸에만 배치하는 경우.
3. 사자를 두 번째 칸에만 배치하는 경우.

DP 배열 설정

DP를 사용하기 위해 각 상태를 저장할 배열을 설정합니다. dp[N][3] 배열을 사용하며, 여기서 N은 우리의 크기를 나타내고, 두 번째 차원의 크기 3은 위의 세 가지 경우를 나타냅니다.

초기 조건 설정

DP 배열의 초기값을 설정합니다. 첫 번째 칸에 대해 사자를 배치하지 않거나, 첫 번째 칸이나 두 번째 칸 중 하나에만 배치하는 경우는 각각 1가지 방법이 있습니다. 따라서 dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1로 초기화합니다.

점화식 구성

다음으로, 각 단계에서의 값들을 계산하는 규칙, 즉 점화식을 구성합니다. N번째 칸에 대해 생각해보면:

• 사자를 배치하지 않는 경우 (dp[N][0]): 이전 칸(N-1)에 사자가 어디에 배치되었든 상관없으므로 dp[N-1][0], dp[N-1][1], dp[N-1][2]의 합입니다.
• 사자를 첫 번째 칸에만 배치하는 경우 (dp[N][1]): 이전 칸에 사자가 첫 번째 칸이나 배치되지 않았어야 하므로 dp[N-1][0]과 dp[N-1][2]의 합입니다.
• 사자를 두 번째 칸에만 배치하는 경우 (dp[N][2]): 이전 칸에 사자가 두 번째 칸이나 배치되지 않았어야 하므로 dp[N-1][0]과 dp[N-1][1]의 합입니다.

결과 계산

모든 칸에 대해 계산을 마치고 나면, 최종적으로 N번째 칸에 대해 세 가지 경우의 수를 모두 더하면 됩니다. 이 때, 문제에서 주어진 대로 9901로 나눈 나머지를 취합니다.

코드 구현

위의 단계들을 코드로 구현하면, 초기화 부분과 점화식을 반복문으로 계산하는 부분, 그리고 최종 결과를 출력하는 부분으로 나누어집니다.

#전체 코드

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

int main() {
    int N;
    cin >> N;

    vector<vector<int>> dp (N+1, vector<int> (3,0));
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;

    for (int i = 2; i <= N; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
    }

    int result = (dp[N][0] + dp[N][1] + dp[N][2]) % 9901;

    cout << result <<'\n';

    return 0;
}

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

#문제 해결 방법

슬라이딩 윈도우를 사용하자

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, d, k, c;
    cin >> N >> d >> k >> c;

    vector<int> sushi(N);
    vector<int> sushiCount(d + 1, 0);  

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

    int sushiType = 0;
    int maxType = 0;

    for (int i = 0; i < k; i++) {
        if (sushiCount[sushi[i]]++ == 0) {
            sushiType++;
        }
    }

    maxType = sushiType;

    for (int i = 1; i < N; i++) {
        if (--sushiCount[sushi[i - 1]] == 0) {
            sushiType--;
        }

        if (sushiCount[sushi[(i + k - 1) % N]]++ == 0) {
            sushiType++;
        }


        if (sushiCount[c] == 0) {
            maxType = max(maxType, sushiType + 1);
        }
        else {
            maxType = max(maxType, sushiType);
        }
    }

    cout << maxType;

    return 0;
}

#코드 해설

1. 변수 초기화
   • N: 벨트 위에 놓인 접시의 수.
   • d: 초밥의 종류 수.
   • k: 연속해서 먹는 접시의 수.
   • c: 쿠폰에 적힌 초밥 번호.
   • sushi: 벨트 상의 초밥의 정보를 저장하는 벡터.
   • sushiCount: 각 초밥 번호가 현재 선택된 범위 내에서 몇 번 나타났는지를 저장하는 벡터.
   • sushiType: 현재 선택된 범위 내에서의 서로 다른 초밥의 종류 수.
   • maxType: 가능한 최대 종류의 초밥 수.
2. 처음 k개의 초밥 종류 계산
   • 초기에 0번부터 k-1번째 까지의 초밥을 선택한 상태에서의 서로 다른 종류의 초밥 수를 계산합니다.
3. 슬라이딩 윈도우를 사용한 계산
   • 회전 초밥 벨트이므로, N번을 반복하면서 슬라이딩 윈도우 기법을 사용하여 선택 범위를 1칸씩 옮겨가면서 서로 다른 종류의 초밥 수를 계산합니다.
   • 이때, 이전 범위의 첫번째 초밥을 제거하고, 새로운 초밥을 범위에 포함시키면서 선택된 범위 내에서의 서로 다른 초밥의 종류 수를 업데이트 합니다.
   • 또한, 현재 선택된 범위 내에서 쿠폰에 적힌 초밥 번호 c가 없으면, 쿠폰을 사용하여 추가로 1종류의 초밥을 먹을 수 있음을 고려하여 maxType을 업데이트합니다.
4. 결과 출력
   • maxType을 출력합니다. 이 값은 연속해서 k개의 접시를 먹었을 때, 가능한 한 최대의 다양한 종류의 초밥을 먹는 경우의 초밥 종류 수를 나타냅니다.

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

#문제 해결 방법

투 포인터를 사용하자

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int st = 0, en = 0;
    int maxLength = 0;
    int curType = 0;

    int alpha[26] = { 0, };

    while (en < s.length()) {
        if (alpha[s[en] - 'a'] == 0) curType++; // 새로운 알파벳 타입을 발견
        alpha[s[en] - 'a']++;

        while (curType > n) { // 허용된 타입을 초과하면 앞에서부터 제거
            if (--alpha[s[st] - 'a'] == 0) curType--;
            st++;
        }

        maxLength = max(maxLength, en - st + 1); // 최대 길이 갱신
        en++;
    }

    cout << maxLength << endl;

    return 0;
}

#코드 설명

1. 변수 설정
   • int st = 0, en = 0; : 투 포인터 알고리즘에서 사용할 시작 포인터(st)와 끝 포인터(en)를 초기화합니다.
   • int maxLength = 0; : 최대 문자열 길이를 저장할 변수입니다.
   • int curType = 0; : 현재 연속된 문자열에서의 알파벳 종류의 수를 저장합니다.
   • int alpha[26] = { 0, }; : a부터 z까지의 알파벳이 현재 연속된 문자열에서 몇 번 나타났는지를 저장하는 배열입니다.
2. 투 포인터 알고리즘
   • while (en < s.length()) : 끝 포인터(en)가 문자열의 길이보다 작은 동안 반복합니다.
     • if (alpha[s[en]-'a'] == 0) curType++; : 끝 포인터가 가리키는 알파벳이 현재 연속된 문자열에 처음 등장하면 알파벳 종류의 수(curType)를 1 증가시킵니다.
     • alpha[s[en]-'a']++; : 해당 알파벳의 등장 횟수를 1 증가시킵니다.
     • while (curType > n) : 알파벳 종류의 수가 N을 초과하면, 시작 포인터를 하나씩 이동시키면서 초과된 알파벳 종류의 수를 줄입니다.
     • maxLength = max(maxLength, en - st + 1); : 최대 문자열 길이를 갱신합니다.
     • en++; : 끝 포인터를 1 증가시킵니다.

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

#문제 간단 정리

위상정렬을 사용해 문제를 풀자.

#전체 코드

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

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N >> K;

        vector<int> build_time(N + 1, 0);
        vector<int> indegree(N + 1, 0);
        vector<int> result(N + 1, 0);
        vector<vector<int>> adj(N + 1);

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

        for (int i = 0; i < K; i++) {
            int X, Y;
            cin >> X >> Y;
            adj[X].push_back(Y);
            indegree[Y]++;
        }

        int W;
        cin >> W;

        queue<int> q;
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.push(i);
                result[i] = build_time[i];
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int next : adj[current]) {
                result[next] = max(result[next], result[current] + build_time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        cout << result[W] << '\n';
    }

    return 0;
}

#코드해설

while (!q.empty()) {
            int current = q.front();
            q.pop();

            for (int next : adj[current]) {
                result[next] = max(result[next], result[current] + build_time[next]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

위상정렬 핵심부분

1. while (!q.empty()) { ... }:
   • 큐 q에는 현재 짓기 시작할 수 있는 건물들의 번호가 저장됩니다. (선행 건물이 없는, 즉 현재 지을 수 있는 건물)
2. int current = q.front(); q.pop();:
   • 큐의 가장 앞에 있는 건물 번호를 가져와 current에 저장하고, 해당 건물 번호를 큐에서 제거합니다.
3. for (int next : adj[current]) { ... }:
   • 현재 건물(current)을 짓고 나서 지을 수 있는 후속 건물들을 순회합니다. 여기서 adj는 인접 리스트로, 각 건물에서 다음에 지을 수 있는 건물들의 목록을 저장하고 있습니다.
4. result[next] = max(result[next], result[current] + build_time[next]);:
   • next 건물을 짓기 시작하기 전까지의 누적 시간을 result[next]에 저장합니다. 여기서 중요한 점은, next 건물을 짓기 시작하는 시간이 여러 경로로 인해 다를 수 있기 때문에 그 중 가장 늦은 시간을 선택해야 합니다. 이를 위해 max 함수를 사용합니다.
5. indegree[next]--;:
   • next 건물로 들어오는 간선의 수(indegree)를 하나 줄입니다. 이는 current 건물이 지어졌기 때문에 next 건물로의 선행 조건이 하나 줄어들었음을 나타냅니다.
6. if (indegree[next] == 0) { q.push(next); }:
   • 만약 next 건물로 들어오는 선행 조건이 모두 해소되었다면 (즉, 모든 선행 건물들이 지어졌다면), next 건물도 지을 수 있게 되므로 큐 q에 추가합니다.

이 알고리즘을 통해 선행 건물들의 건설 완료 시간을 고려하여 각 건물을 건설하는 데 필요한 최소 시간을 result 배열에 저장할 수 있습니다.

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

이 문제는 Dynamic Programming (DP)을 사용하여 해결할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)를 찾는 문제입니다.

#발상
주어진 수열 A에서, 각 위치에서 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아보자는 것이 발상의 기본입니다. 이렇게 각 위치마다의 LIS 길이를 구하면, 그 중 최대값이 전체 수열 A의 LIS 길이가 됩니다.

#해설
초기화: D[i] 배열은 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 초기에는 모든 원소의 값이 1입니다. 왜냐하면, 각 원소 자체만으로 길이 1의 증가하는 부분 수열을 이룰 수 있기 때문입니다.

DP 수행: i번째 원소에 대해, 0부터 i-1번째 원소까지 비교를 수행합니다. 만약 A[j] < A[i]이면, j번째 원소가 i번째 원소 앞에 올 수 있으므로, D[i] = max(D[i], D[j] + 1)를 수행합니다. 이는 i번째 원소 앞에 올 수 있는 j번째 원소들 중, 가장 긴 증가하는 부분 수열에 i번째 원소를 추가하는 것입니다.

결과 출력: D[i] 배열 중 가장 큰 값을 출력합니다. 이 값이 주어진 수열 A의 가장 긴 증가하는 부분 수열의 길이입니다.

#코드 설명
vector<int> A(1001)와 vector<int> D(1001,1)는 각각 수열 A와 각 위치의 LIS 길이를 저장합니다.
수열 A의 크기 N을 입력받고, N개의 원소를 A에 저장합니다.
이중 반복문을 통해 각 위치에서 LIS 길이를 계산합니다.
계산된 LIS 길이 중 최대값을 MAX 변수에 저장합니다.
MAX 값을 출력합니다.
이 방법을 통해, O(N^2)의 시간 복잡도로 문제를 해결할 수 있습니다.

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

#문제 간단 정리

dp 를 쓰자

주의할건 dp 배열의 초기값을 높게 설정해 줘야 한다

최소값을 고르는거기 때문에 0이 설정되어 있다면 최소값으로 0이 선택되기 때문이다.

#전체 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;


int main() {

    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    vector<int> card(n + 1);
    vector<int> d(n + 1,123456789);
    for (int i = 1; i <= n; i++) {
        cin >> card[i];
    }
    d[0] = 0;
    d[1] = card[1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=i; j++) {
            d[i] = min(d[i], d[i - j] + card[j]);
        }
    }

    cout << d[n];

    return 0;
}

#코드 설명

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있는 문제입니다. 주어진 코드도 동적 계획법을 사용하여 문제를 해결하고 있습니다. 문제에서 요구하는 것은 주어진 카드 팩의 가격을 바탕으로 N개의 카드를 최소 비용으로 구매하는 방법을 찾는 것입니다.

주어진 코드의 주요 부분을 설명하겠습니다:

vector<int> card(n + 1);와 vector<int> d(n + 1,123456789);는 각각 카드 팩의 가격과 각 개수의 카드를 구매하는데 필요한 최소 비용을 저장하는 배열입니다.

d[0] = 0;와 d[1] = card[1];은 초기값 설정입니다. 0개의 카드를 구매하는데는 비용이 없고, 1개의 카드를 구매하는데는 card[1]의 비용이 듭니다.

이중 for문을 사용하여 각 개수의 카드를 구매하는데 필요한 최소 비용을 계산합니다. 여기서 d[i] = min(d[i], d[i - j] + card[j]);는 i개의 카드를 구매하는데 필요한 최소 비용을 구하는 식입니다. i-j개의 카드를 구매하는데 드는 최소 비용에 j개 카드 팩의 가격을 더한 값과 현재의 d[i] 값을 비교하여 더 작은 값을 d[i]에 저장합니다.

최종적으로 cout << d[n];을 통해 N개의 카드를 구매하는데 필요한 최소 비용을 출력합니다.

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

#전체 코드

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

using namespace std;
vector<int> tree[51];
int check[51];
int leaf = 0;
int wither;
int root;

void findLeaf(int node ) {
    check[node] = true;
    
    if (node == wither) return;

    bool isLeaf = true;

    for (int i = 0; i < tree[node].size(); i++) {
        int nextNode = tree[node][i];
        if (check[nextNode] != true && nextNode != wither) {
            isLeaf = false;
            findLeaf(nextNode);
        }
    }

    if (isLeaf) leaf++;

}


int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;     cin >> n;

    for(int i=0; i<n; i++){
        int input; cin >> input;
        if (input == -1) {
            root = i;
        }
        else {
            tree[input].push_back(i);
        }

    }
    cin >> wither;
    
    findLeaf(root);

    cout << leaf << "\n";


    return 0;
}

벡터로 트리를 구현했다.

리프는 dfs를 사용해서 찾았다

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

#문제 간단 정리

문제 풀이 전략
문제의 목적은 주어진 규칙에 따라 연속된 집들을 서로 다른 색으로 칠하는 최소 비용을 찾는 것입니다. 이러한 유형의 문제는 동적 프로그래밍(dynamic programming, DP)을 사용하여 해결할 수 있습니다.

문제를 해결하는 전략은 다음과 같습니다:

먼저, 각 집을 칠할 때의 비용을 2차원 배열에 저장합니다.
그런 다음, 다른 색상 조합에 대해 이전 집들까지의 최소 비용을 저장하는 또 다른 2차원 배열을 만듭니다.
각 집에 대해 가능한 색상을 선택하고, 선택한 색상을 제외한 이전 집의 두 색상 중 최소 비용을 현재 집의 비용에 더합니다.
모든 집을 확인한 후, 마지막 집에서 가능한 최소 비용을 찾습니다

#전체 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;


int main() {
	int n; cin >> n;
	int house_cost[1001][3] = { 0 };
	int result[1001][3] = { 0, };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> house_cost[i][j];
		}
	}

	result[0][0] = house_cost[0][0];
	result[0][1] = house_cost[0][1];
	result[0][2] = house_cost[0][2];

	for (int i = 1; i <= n; i++) {
		result[i][0] = min(result[i-1][1],result[i-1][2]) + house_cost[i][0];
		result[i][1] = min(result[i - 1][0], result[i - 1][2]) + house_cost[i][1];
		result[i][2] = min(result[i - 1][0], result[i - 1][1]) + house_cost[i][2];

	}
	int min = 123456789;
	for (int i = 0; i < 3; i++) {
		if (result[n][i] < min) {
			min = result[n][i];
		}
	}
	cout << min << endl;
}

코드 해설
코드는 위에서 설명한 전략을 따르며, 주요 부분을 분석하겠습니다.

cpp
Copy code
int n; cin >> n;
int house_cost[1001][3] = { 0 };
int result[1001][3] = { 0, };
여기서 n은 집의 수를 나타내며, house_cost 배열에 각 집을 칠하는 비용을 저장합니다. result 배열은 각 집에 대한 최소 비용을 저장할 배열입니다.

cpp
Copy code
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cin >> house_cost[i][j];
}
}
이 부분은 각 집을 칠하는 비용을 입력 받아 house_cost 배열에 저장하는 코드입니다.

cpp
Copy code
result[0][0] = house_cost[0][0];
result[0][1] = house_cost[0][1];
result[0][2] = house_cost[0][2];
여기에서 첫 번째 집의 최소 비용을 각 색상의 비용으로 초기화합니다.

cpp
Copy code
for (int i = 1; i <= n; i++) {
result[i][0] = min(result[i-1][1],result[i-1][2]) + house_cost[i][0];
result[i][1] = min(result[i - 1][0], result[i - 1][2]) + house_cost[i][1];
result[i][2] = min(result[i - 1][0], result[i - 1][1]) + house_cost[i][2];
}
이 반복문은 동적 프로그래밍을 통해 각 집에서 가능한 최소 비용을 계산합니다. 현재 집의 각 색상에 대해 가능한 최소 비용을 찾기 위해 이전 집의 두 색상 중 최소 비용을 현재 집의 비용에 더합니다.

cpp
Copy code
int min = 123456789;
for (int i = 0; i < 3; i++) {
if (result[n][i] < min) {
min = result[n][i];
}
}
cout << min << endl;
마지막으로, 마지막 집에서 가능한 최소 비용을 찾고 출력합니다.

주의사항
반복문의 범위를 주의해야 합니다. for (int i = 1; i <= n; i++)에서 i는 n까지 돌아야 하지만, 배열 인덱스는 0부터 시작하므로 house_cost와 result 배열에 접근할 때 i-1을 사용해야 합니다.

cpp
Copy code
for (int i = 1; i < n; i++) { // n까지가 아니라 n-1까지
...
result[i][0] = min(result[i-1][1], result[i-1][2]) + house_cost[i-1][0];
...
}
그리고 최종 결과를 찾을 때, result[n][i] 대신 result[n-1][i]를 사용해야 합니다.

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

#전체 코드

#include <iostream>
#include <algorithm>

using namespace std;


int main() {

    
    string A, B;
    cin >> A >>  B;

    int ans = 0;

    int B_index = B.length() - 1;
    for (int i = A.length()-1; i >= 0; i--) {
        if (A[i] == B[B_index]) {
            B_index --;
        }
        else ans++;

    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if (A == B) cout << ans;
    else cout << -1;



    return 0;
}

문제 해설
문제는 2×n 크기의 직사각형을 1×2 또는 2×1 크기의 타일로 채울 수 있는 방법의 수를 찾는 것입니다. 그러나 찾은 수가 매우 클 수 있으므로, 10,007로 나눈 나머지를 출력해야 합니다.

코드 설명
이 문제를 해결하기 위해 동적 프로그래밍(DP)이라는 방법을 사용하고 있습니다. 아래에서 코드의 각 부분에 대해 설명하겠습니다:

cpp
Copy code
int n; cin >> n;

int tile[1001] = { 0 };
위에서는 n을 입력 받고, 최대 크기가 1001인 배열을 초기화하고 있습니다. 배열 tile은 각 인덱스에서 가능한 타일링 방법의 수를 저장할 것입니다.

cpp
Copy code
tile[0] = 1;
tile[1] = 1;
tile[2] = 2;
2×0, 2×1, 2×2 크기의 직사각형을 타일로 채우는 방법의 수는 각각 1, 1, 2가 됩니다. 이는 초기 조건으로 설정됩니다.

cpp
Copy code
for (int i = 3; i <= n; i++) {
tile[i] = (tile[i - 1] + tile[i - 2])%10007;
}
이 반복문은 DP 접근법의 핵심 부분입니다. 각 i에 대해 (i-1)과 (i-2)에서 가능한 타일링 방법의 수의 합을 구하며, 이를 10,007로 나눈 나머지를 저장합니다. 이는 2×i 크기의 직사각형을 채우는 마지막 부분이 2×1 또는 1×2 타일로 채워지는 두 가지 경우를 고려한 것입니다.

cpp
Copy code
cout << tile[n];
마지막으로, 2×n 크기의 직사각형을 채울 수 있는 방법의 수를 출력합니다. 이 값은 위의 반복문에서 tile[n]에 저장되어 있습니다.

결론
이 코드는 동적 프로그래밍을 사용하여 문제를 효율적으로 해결합니다. 단계별로 이전 결과를 이용해 현재 문제를 해결함으로써, 최종적으로 원하는 크기의 직사각형에 대한 해결책을 찾을 수 있습니다.