[C++] SWEA 4311 - 오래된 스마트폰

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWL2vlPKMlQDFAUE&categoryId=AWL2vlPKMlQDFAUE&categoryType=CODE&problemTitle=4311&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 스마트폰 정보를 입력받는다.

2. 주어진 스마트폰으로 W를 만들 수 있는 최소 터치 횟수를 출력한다.

 

<해법>

1. 문제를 해결하는 흐름

=> 다 해봐야 한다는 생각이 듭니다. 재귀를 통해서 머릿속으로 구현하던 중, '다음에 숫자를 누르는 경우와 연산자를 누르는 경우를 나누어서 생각해야 한다.'는 생각이 듭니다. 갑자기 복잡해집니다. 저는 이 때, 재귀함수 하나로 해결하는 것이 아닌 경우에 따라서 두 개로 나누었습니다. 숫자만 눌러서 만드는 경우, 숫자와 연산자를 눌러서 만드는 경우로 나누어서 구현하였습니다.

 

//라이브러리 사용 불가
#include <iostream>
#define INF 987654321
 
using namespace std;
 
int N, O, M, W;
int numPad[10];
int operPad[4];
int nums[1000];
int numsSize;
int bestTouchCnt[1000];
int answer;
 
//연산
int calculate(int oper, int n1, int n2) {
    int output = 0;
    switch (oper) {
    case 1:
        output = n1 + n2;
        break;
    case 2:
        output = n1 - n2;
        break;
    case 3:
        output = n1 * n2;
        break;
    case 4:
        if (n2 == 0) return -1;
        output = n1 / n2;
        break;
    }
 
    return (0 <= output && output <= 999) ? output : -1;
}
 
//연산자 없이 숫자 만들기
void makeNum(int select, int num) {
 
    if (select == min(M, 3)) return; 
 
    for (int i = 0; i < N; i++) {
        int nxtNum = num * 10 + numPad[i];
        if (bestTouchCnt[nxtNum] <= select + 1) continue;
        bestTouchCnt[nxtNum] = select + 1;
        makeNum(select + 1, nxtNum);
    }
}
 
//연산자 이용해서 숫자 만들기
void makeNumWithOper(int n1, int touchCnt) {
 
    if (n1 == W) return;
 
    for (int i = 0; i < numsSize; i++) {
        int n2 = nums[i];
        int nxtTouchCnt = bestTouchCnt[n1] + bestTouchCnt[n2] + 1;
 
        if (nxtTouchCnt + 1 > M) continue;
 
        for (int j = 0; j < O; j++) {
            int oper = operPad[j];
            int nxtNum = calculate(oper, n1, n2);
            if (nxtNum == -1 || bestTouchCnt[nxtNum] <= nxtTouchCnt) continue;
            bestTouchCnt[nxtNum] = nxtTouchCnt;
            makeNumWithOper(nxtNum, nxtTouchCnt);
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, O = 0, M = 0, W = 0;
        for (int i = 0; i < 10; i++) numPad[i] = 0;
        for (int i = 0; i < 4; i++) operPad[i] = 0;
        for (int i = 0; i < 1000; i++) nums[i] = 0;
        numsSize = 0;
        for (int i = 0; i < 1000; i++) bestTouchCnt[i] = INF;
        answer = 0;
 
        //입력
        cin >> N >> O >> M;
        for (int i = 0; i < N; i++) {
            cin >> numPad[i];
        }
        for (int i = 0; i < O; i++) {
            cin >> operPad[i];
        }
        cin >> W;
 
        /* 해법 */
        //1. 연산자 없이 모든 숫자를 만든다.
        makeNum(0, 0);
 
        //2. (1) 연산자 없이 W를 만들 수 있으면, 바로 정답 갱신
        //   (2) 연산자 없이 못 만들면, 연산자를 이용해보고 정답 갱신
        if (bestTouchCnt[W] != INF) answer = bestTouchCnt[W];
        else {
            for (int i = 0; i < 1000; i++) {
                if (bestTouchCnt[i] != INF) nums[numsSize++] = i;
            }
            for (int i = 0; i < numsSize; i++) {
                int n1 = nums[i];
                makeNumWithOper(n1, bestTouchCnt[n1]);
            }
            answer = (bestTouchCnt[W] == INF) ? -1 : bestTouchCnt[W] + 1;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

구현과 재귀함수에 대해 알아볼 수 있는 문제였습니다.