[boj][c++] 10819 차이를최대로, 10971 외판원순회2, 2758 로또

10819 차이를 최대로

순열을 사용해서 계산할 수 있는 문제였다. 원소의 순서가 달라지면 결과값이 달라지기 때문에 next_permutation() 함수를 통해서 원소의 순서를 계속 바꿔가며 브루트포스 탐색을 진행하면 된다.

주의할 부분은 연산을 시작하기 전 배열을 오름차순으로 정렬해야 하는 것이다.

next_permutation은 다음 순열을 찾아주는 함수이므로 식이 정렬되지 않았을 때 앞부분을 고려하지 않고 연산하게 된다. 따라서 정렬이 필수다.

문제를 꼼꼼히 안 봐서 ans = |a[1]-a[2]|+|a[3]-a[4]|... 연산을 수행하는줄 알았으나 결과값을 보며 잘못됐음을 인지했다. 그래도 큰 틀은 바뀌지 않아서 금방 수정했다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n, ans;
int arr[9];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    do
    {
        int temp = 0;
        for (int i = 1; i < n; i++)
            temp += abs(arr[i] - arr[i - 1]);
        ans = max(ans, temp);
    } while (next_permutation(arr, arr + n));
    cout << ans << '\n';
}

10971 외판원 순회2

이 문제는 위에서 본 순열문제를 응용해서 풀 수 있다. 로직은 다음과 같다.

• 각 원소가 중복되지 않는 모든 경우의 수를 확인하기 위해 순열을 사용한다. 순열을 사용할 배열을 구현한다.
• 이동거리를 담을 배열을 구현한다.
• 반복문을 통해 다음수열을 계속해서 확인한다.
  • 수열의 첫 원소부터 끝 원소까지의 모든 거리를 더한다.
  • 마지막 원소에서 첫 원소로 돌아가는 거리를 추가로 더한다.
• 가장 작은 수를 정답으로 저장한다.

위의 로직을 구현하면서도 추가로 이동거리가 0인게 하나 이상 있으면 해당 수열의 합은 사용하지 않아야 한다.

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

int n, ans;
int arr[11];
int graph[11][11];

int main()
{
    ans=1e9;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
        arr[i] = i + 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> graph[i][j];
        }
    }
    do
    {
        bool check = true;
        int sum = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (graph[arr[i]][arr[i + 1]] == 0)
                check = false;
            else
                sum += graph[arr[i]][arr[i + 1]];
        }
        if (check && graph[arr[n - 1]][arr[0]] != 0)
        {
            sum += graph[arr[n - 1]][arr[0]];
            ans = min(ans, sum);
        }
    } while (next_permutation(arr, arr + n));
    cout<<ans<<'\n';
}

2758 로또

DP문제...!

점화식 이해하는데 시간이 필요했다.

DP[N][M] 이고 N = 현재 자리수 M = 사용 가능한 수 이다. 이 때 dp의 각 자리에는 N과 M일 때 가능한 경우의 수가 들어가게 된다.

점화식은 DP[n][m] = f(n-1, m/2) + f(n, m-1) 이다. 예제대로 n=4, m=10 일 때의 경우를 표로 그려서 점화식을 이해해봤다.

전자는 현재 자리수를 제외한 앞 자리의 가능한 경우, 후자는 현재 자리의 직전 m 을 탐색했을 때 가능한 경우.

둘을 더하면 현재 자리의 가능한 경우가 나오게 된다.

주의할 점은, dp테이블을 -1로 초기화하되 n이 1일 때는 dp테이블을 m값으로 초기화해야 한다. 위에서 그린 dp테이블을 직접 그려보면 어느정도 감이 잡힐 것이다.

점화식 짜는거 너무 어렵다!

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

long long t;
long long dp[11][20001];

long long ro(long long n, long long m);

void solve()
{
    long long n, m;
    cin >> n >> m;
    cout << ro(n, m) << '\n';
}

long long ro(long long x, long long y)
{
    if (y <= 0)
        return 0;
    long long &sum = dp[x][y];
    if (sum != -1)
        return sum;
    sum = 0;
    sum += ro(x - 1, y / 2);
    sum += ro(x, y - 1);
    return sum;
}

int main()
{
    cin >> t;
    memset(dp, -1, sizeof(dp));
    for (long long i = 1; i <= 2000; i++)
        dp[1][i] = i;
    while (t--)
    {
        solve();
    }
}