[C++] 2494 - 숫자 맞추기 (골드1)

1. 문제 설명

2494번: 숫자 맞추기

 

---

2. 아이디어

벽장문 문제나 카드 게임 문제 같은 이런 문제들은 갈림길에서 어떤 선택을 하느냐에 따른

모든 경우의 수를 판단하도록 요구한다. 그리고 이런 요구의 해답에 보통 DP는 기본으로 들어간다.

하지만 난 DP로 접근했다가 실패했다. (어떻게 구현하려면 할 수 있을 것 같긴 하다.)

C++이 익숙치 않아서 복잡하게 풀기가 싫다보니, 다른 방법을 고민하다가 그냥 가장 위에서부터

나사를 돌려보기로 했다.

 

생각해보면 나사를 밑에서 맞추는 건 의미가 없는 행위다.

밑에서 돌렸다가 위쪽 나사에서 왼쪽으로 돌려버리면 맞춰놓은 게 다 틀어지는데,

그런 경우의 수까지 다 고려하면서 코딩하는 건 돌발 변수가 너무 많다.

 

그냥 가장 위의 나사부터 왼쪽이나 오른쪽으로 돌렸을 때 경우의 수를 나누어 분할탐색을 실시한다.

가장 아래의 나사에 도달하면 왼쪽으로 돌렸을 때와 오른쪽으로 돌렸을 때 중에

더 조금만 돌려도 되는 케이스의 나사 위치, 현재 나사의 값, 돌린 횟수를 구조체에 저장해두었다가

함수 실행이 끝나면 구조체에 저장된 나사 위치와 나사의 값을 통해 돌린 횟수를 출력한다.

 

C++이 익숙하지 않아서 그렇지 재밌는 문제였다.

 

---

3. 코드

#include <iostream>
#include <algorithm>
#include <string>

#define MOD 10

using namespace std;

typedef struct s_state
{
    int idx, value, cnt;
}              t_state;

int N;
string init, final;
int cache[10001][10];
t_state state[10001][10];

int turn_screw(int row, int num) {
    if (row == N) return 0; // exception handling (out of index)

    int &ret = cache[row][num];
    if (ret) return ret;

    int left = (final[row] - init[row] - num + 20) % MOD; // gap check
    int right = 10 - left;

    int turned_left = turn_screw(row + 1, (num+left) % MOD) + left; // compare left && right
    int turned_right = turn_screw(row + 1, num) + right;

    if (turned_left < turned_right) {
        state[row][num] = {row + 1, (num+left) % MOD, left};
        ret = turned_left;
    } else { 
        state[row][num] = {row + 1, num, -right};
        ret = turned_right;
    }

    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> init >> final;

    cout << turn_screw(0, 0) << "\n";

    int row = 0, num = 0;
    for (int i = 1; i <= N; i++) {
        t_state &curr = state[row][num];
        cout << i << ' ' << curr.cnt << "\n";
        row = curr.idx;
        num = curr.value;
    }

    return 0;
}