[ 백준 ] 14395 / 4연산

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
77/228
post-thumbnail

# Appreciation

/*
 * Problem :: 14395 / 4연산
 *
 * Kind :: Dynamic Programming + BFS
 *
 * Insight
 * - sizeof(int) 만큼의 dp 를 만들어야 하나?
 *   너무 큰데...
 *   + 그런데 조금 연산이 이상하다?
 *     (+, *) 는 괜찮은데
 *     (-, /) 는 s 에 상관없이 (0, 1) 이 되버린다
 *     # 그리고 (+, *) 도 값을 증가시키는 연산이기때문에
 *       만약 계산한 값이 t 를 넘어가면
 *       (-, /) 연산을 사용하여 (0, 1) 로 돌아가야만 한다
 *       -> 이런 연산의 특성을 생각해보면
 *          sizeof(t) 만큼의 dp 인데 가능한 값들은
 *          0, 1, 2, 4, 8, ...
 *             s, 2*s, 4*s, 8*s, ...
 *             s^2, 2*s^2, 4*s^2, 8*s^2, ...
 *             밖에 없다
 *             => 알고보니 사용하는 공간은 극히 일부분이다!
 *                map 을 사용해주자
 *
 * Point
 * - 하드코딩을 방지해주기 위해
 *   각 연산에 따른 계산한 값들을 배열에 넣어주자
 *
 * - 값이 0 인 경우일 때 에외 처리를 잊지 말자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>
#include <map>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int s, t;
    cin >> s >> t;

    // Control : Output
    /* s 와 t 가 같으면 */
    if (s == t) {
        cout << 0 << endl;
        exit(0);
    }

    // Process
    /* s 와 t 가 다르면 */
    map<long,string> dp; /* map 을 사용한 dp */
    queue<long> que;
    que.push(s);
    dp[s] = "";

    string OP[] = {"*", "+", "-", "/"}; /* 각 연산 배열 */
    while (not(que.empty())) {
        long c = que.front();
        que.pop();
        if (c == 0) continue;
        if (c == t) break;

        string e = dp[c];
        long N[] = {c*c, c+c, c-c, c/c}; /* 각 연산에 따른 계산한 값 배열 */
        for (int i=0; i<4; i++) {
            string op = OP[i];
            long n = N[i];
            if (n <= t && not(dp.contains(n))) {
                dp[n] = e + op; /* 연산방법 저장 */
                que.push(n);
            }
        }
    }

    // Control : Output
    cout << ((dp[t].empty()) ? to_string(-1) : dp[t]) << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글