[백준/BOJ] 14889번 : 스타트와 링크, 9184번 : 신나는 함수 실행, 1904번 : 01타일

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14889번 : '스타트와 링크', 9184번 : '신나는 함수 실행', 1904번 : '01타일' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어 정도에 해당하며, 문제를 풀이하기 위해 백트래킹 또는 DP에 대한 개념을 알고 있으면 좋습니다.

 

 

14889번 : 스타트와 링크

 

한 팀에 사람들이 있을 때 만드는 시너지에 대한 점수표가 주어진다고 할 때, 두 팀 사이의 점수 합의 차가 최소가 되도록 하는 차이값을 구하는 문제입니다.

N이 20 이하의 짝수이므로, Combination으로 2N명 중 N명을 선택하는 모든 경우의 수를 브루트포스 알고리즘으로 돌려서 확인해도 무관합니다.

따라서 재귀함수를 활용하여 모든 경우의 수를 탐색할 수 있도록 구현해보겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

int N, arr[20][20], ans = INT_MAX;
bool check[20];

void solve(int cnt, int idx) {
    if(idx == N) return;
    if(cnt == N/2) {
        int score1 = 0, score2 = 0;
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) {
                if(check[i] && check[j]) score1 += arr[i][j];
                if(!check[i] && !check[j]) score2 += arr[i][j];
            }
        ans = min(ans, abs(score1 - score2));
        return;
    }

    check[idx] = true; solve(cnt+1, idx+1);
    check[idx] = false; solve(cnt, idx+1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) cin >> arr[i][j];
    solve(0, 0);
    cout << ans;
}

 

먼저 arr은 점수표를 저장하기 위한 배열이고, check 함수를 통해 팀 1에 선발할지 그 여부를 저장합니다.

만약 check 값이 false라면 팀 2에 들어가게 되는 것입니다.

재귀함수를 통해서 idx = 0부터 시작하여 N-1까지 증가하면서 각 idx를 선택할지 안할지를 재귀함수로 구현합니다.

만약 idx = N까지 도달했다면 N/2개의 체크가 진행되지 않은 것이므로 그냥 버립니다.

만약 idx = N-1 또는 그 이전에 cnt = N/2개로 체크가 완료되었다면, 그 경우에서 팀의 점수를 합산하여 비교합니다.

 

그 합의 차가 최소가 되는 값을 ans에 저장하고, 모든 탐색이 끝나면 답으로 출력해주면 됩니다.

 

 

 

 

9184번 : 신나는 함수 실행

 

재귀함수 코드를 더 빠르게 돌아갈 수 있도록 하여 w(a, b, c)값을 시간 안에 구하도록 하는 문제입니다.

DP를 활용하여 계산 값들을 중간마다 배열에 저장한 뒤 이를 활용하는 방식으로 계산 횟수를 줄여서 풀어야 합니다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[21][21][21] = {};

int solve(int a, int b, int c) {
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if(a > 20 || b > 20 || c > 20) return solve(20, 20, 20);
    if(dp[a][b][c] != 0) return dp[a][b][c];
    if(a < b && b < c)
        return dp[a][b][c] = solve(a, b, c-1) + solve(a, b-1, c-1) - solve(a, b-1, c);
    return dp[a][b][c] = solve(a-1, b, c) + solve(a-1, b-1, c) + solve(a-1, b, c-1) - solve(a-1, b-1, c-1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int a, b, c; cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << solve(a, b, c) << "\n";
    }
}

 

문제에서 정의한 함수대로 재귀적으로 계산해주되, return 할 때 dp[a][b][c]에 그 계산 값을 저장하면서 연산을 해줄 수 있도록 합니다.

 

 

 

 

1904번 : 01타일

 

이진수를 만들 때 0은 반드시 2개씩 붙여서 사용한다는 조건이 있을 때 길이 N인 이진수의 개수를 구하는 문제입니다.

점화식을 세워보면 길이 N인 수열은 길이 N-2인 수열에 00을 붙이거나, 길이 N-1인 수열에 1일 붙여서 만들 수 있습니다.

따라서 f(N) = f(N-1) + f(N-2) (f(1) = 1, f(2) = 2)를 활용하여 dp로 문제를 풀 수 있게 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[1000005] = {0, 1, 2};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=3; i<=N; i++)
        dp[i] = (dp[i-1] + dp[i-2])%15746;
    cout << dp[N];
}

 

단순히 점화식만 세우면 풀리는 문제이므로 위와 같이 간단하게 풀이할 수 있습니다.

다만 모든 답은 15746으로 나눈 나머지를 출력해야 하므로 연산마다 %15746을 수행해주어야 합니다.