[BOJ] 13392 : 방법을 출력하지 않는 숫자 맞추기

문제 링크

13392번: 방법을 출력하지 않는 숫자 맞추기 (acmicpc.net)

13392번: 방법을 출력하지 않는 숫자 맞추기

DP 문제로 골드2라고 되어있지만 내 체감상으로 전에 풀었던 골드1 로봇 조종하기보다 어려운 것 같다.

오답

처음에는 DP배열을 2차원배열로 만들어서 생각했다.

DP[돌리고있는 나사 번호][왼쪽으로 돌릴지 오른쪽으로 돌릴지] 이렇게 생각했다.

이전에 왼쪽으로 돌려서 만들어진 현재 보고있는 앞면이 있을 것이고, 오른쪽으로 돌려서 만들어진

현재 보고있는 앞면이 있을 것이다.

1. 왼쪽으로 돌릴거라고 했을 때, 이전에 왼쪽으로 돌려서 만들어진 면이 있고 오른쪽으로 돌려서 만들어진 면이 있다.

왼쪽으로 돌려서 만들어진 면에서 왼쪽으로 돌려 원하는 숫자를 만든다. 오른쪽으로 돌려서 만들어진 면에서 왼쪽으로 돌려 원하는 숫자를 만든다. 이 두 가지 경우중 돌린 총 횟수가 적은 경우를 택하는 방식을 선택했는데, 이렇게 할 경우 만약 두 가지 경우의 총 횟수가 같다면 여기서 문제가 발생한다. 그래서 이 방법은 아님을 깨달았다.

몇시간을 고민했지만 도저히 방법을 모르겠어서 다른 분들의 코드를 참고했다. 참고하면서 이해하려고해도 이해가 쉽지않은 문제였다.

참고 링크

https://kimcodingvv.github.io/BOJ-13392/

[BOJ | 백준] 13392번: 방법을 출력하지 않는 숫자 맞추기

그 중에서 가장 이해하기 쉬웠던 김코딩님의 코드로 이해해보려했다.

풀이

먼저 i번째 나사를 돌리려 한다고 가정했을때 i-1번째까지 왼쪽으로 몇 번 돌렸냐가 i번째 나사의 숫자가 무엇인지에 영향을 미친다. 오른쪽으로는 이전에 몇번을 돌렸든 i번째 숫자는 바뀌지 않는다. 왼쪽으로 12번을 돌린 것이랑 왼쪽으로 2번 돌린 것은 결국 같은 숫자이므로 모듈러를 이용해 %10을 해준다.

i번째 나사를 원하는 숫자로 만들기 위해서는

왼쪽으로 (만들어야 할 숫자 - 현재 i번째 나사의 숫자 - 전에 왼쪽으로 돌린 횟수 + 20) % 10 만큼 돌려야한다.

+20을 해주는 이유는 만들어야 할 숫자가 0이고 i번째 나사가 9라면 +10만 하면 음수가 될 수도있기 때문에 +20을 해서 양수로 만들어 준다.

왼쪽으로 돌려야 하는 횟수를 left 라고 하면 오른쪽으로는 10-left 만큼 돌리면 원하는 숫자를 만들 수 있다.

1. 왼쪽으로 돌리는 경우 DP[i][(j+left) %10)] = min(DP[i][(j+left)%10], DP[i-1][j] + left) 이다.

왼쪽으로 돌린 총 횟수가 j에서 j+left로 바뀌었다.

2. 오른쪽으로 돌리는 경우 DP[i][j] = min(DP[i][j], DP[i-1][j] + right) 이다.

왼쪽으로 돌린 총 횟수는 변하지 않는다.

이렇게 해서 마지막에

DP[N][0~9] 중 가장 작은 값을 출력하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
#define Floor 1000000000000000000
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 10000 + 5;
int N;
vector<int> num;
vector<int> goal;
int DP[MAX_N][10];
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    char ch;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 9; j++)
            DP[i][j] = INF;
    }
 
    num.push_back(0);
    for (int i = 0; i < N; i++) {
        cin >> ch;
        num.push_back(ch - '0');
    }
    goal.push_back(0);
    for (int i = 0; i < N; i++) {
        cin >> ch;
        goal.push_back(ch - '0');
    }
    for (int i = 0; i <= 9; i++) {
        DP[0][i] = i;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 9; j++) {
            int left = (goal[i] - num[i] - j + 20) % 10;
            int right = 10 - left;
            DP[i][j] = min(DP[i][j], DP[i - 1][j] + right);
            DP[i][(j + left) % 10] = min(DP[i][(j + left) % 10], DP[i - 1][j] + left);
        }
    }
    int ans = INF;
    for (int i = 0; i <= 9; i++) {
        ans = min(ans, DP[N][i]);
    }
    cout << ans << "\n";
    return 0;
}

논리는 모두 이해했지만, 처음에 DP[0][i] 값을 왜 i로 초기화 시켜주는지는 아직 이해가 안된다.

DP에 조금 자신있어 지려했지만 아직 멀었다는 걸 다시 느꼈다.