N으로 표현 C++(동적계획법, DP)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀 더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현 | 프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

문제!!

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

제한사항

N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다.

예시

n	number	return
5	12	4
2	11	3
5	31168	-1

 

예제 1 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 예제 2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

2. 문제풀이

---

문제의 분류는 동적 계획법(Dynamic Programing, DP)로 되어있습니다. 그런데 DP로 하는 방식의 감을 못잡겠어서 dfs로 풀었습니다. 들어가는 깊이의 최대횟수가 9이하이기 때문에 가능했습니다. 방식은 N과 뒤에 +, -, *, /를하고 NN뒤에 +, -, *, /를 하고 NNN뒤에... 반복적인 작업을 통해서 처리를 했습니다. 작업을 통해나온 수가 원하는 number와 같다면 사용한 N의 개수를 파악해서 작은것으로 answer를 교체하는 방식이었습니다.   dp로 풀어보는것은 나중에 따로 추가하도록 하겠습니다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <algorithm>
using namespace std;
 
int answer = 9;
 
void dfs(int N, int number, int count, int currentNumber) {
    if (count >= 9)        return;
    if (currentNumber == number) {
        answer = min(answer, count);
        return;
    }
    int tempNumber = 0;
    for (int i = 0; i + count< 9 ; i++) {
        tempNumber = tempNumber * 10 + N;
        dfs(N, number, count + 1 + i, currentNumber + tempNumber);
        dfs(N, number, count + 1 + i, currentNumber - tempNumber);
        dfs(N, number, count + 1 + i, currentNumber * tempNumber);
        dfs(N, number, count + 1 + i, currentNumber / tempNumber);
    }
}
 
int solution(int N, int number) {
    dfs(N, number, 0, 0);
    if (answer == 9)    return -1;
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <algorithm>
using namespace std;
 
int answer = 9;
 
void dfs(int N, int number, int count, int currentNumber) {
    //일정횟수 이상갔다면 리턴
    if (count >= 9)        return;
    //현재수가 number와 같다면 작은횟수를 answer에 저장후 리턴
    if (currentNumber == number) {
        answer = min(answer, count);
        return;
    }
    int tempNumber = 0;
    //최대 N의 사용횟수는 9번까지이므로 이때까지 반복
    for (int i = 0; i + count< 9 ; i++) {
        //N부터 NN,NNN,NNNN .....
        tempNumber = tempNumber * 10 + N;
        //더하기 빼기 곱하기 나누기 dfs 사용
        dfs(N, number, count + 1 + i, currentNumber + tempNumber);
        dfs(N, number, count + 1 + i, currentNumber - tempNumber);
        dfs(N, number, count + 1 + i, currentNumber * tempNumber);
        dfs(N, number, count + 1 + i, currentNumber / tempNumber);
    }
}
 
int solution(int N, int number) {
    dfs(N, number, 0, 0);
    //answer가 9라는 뜻은 number와 맞는 경우가 없었던 것이므로 -1 리턴
    if (answer == 9)    return -1;
    return answer;
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int answer = 9;
 
void dfs(int N, int number, int count, int currentNumber) {
    //일정횟수 이상갔다면 리턴
    if (count >= 9)        return;
    //현재수가 number와 같다면 작은횟수를 answer에 저장후 리턴
    if (currentNumber == number) {
        answer = min(answer, count);
        return;
    }
    int tempNumber = 0;
    //최대 N의 사용횟수는 9번까지이므로 이때까지 반복
    for (int i = 0; i + count< 9 ; i++) {
        //N부터 NN,NNN,NNNN .....
        tempNumber = tempNumber * 10 + N;
        //더하기 빼기 곱하기 나누기 dfs 사용
        dfs(N, number, count + 1 + i, currentNumber + tempNumber);
        dfs(N, number, count + 1 + i, currentNumber - tempNumber);
        dfs(N, number, count + 1 + i, currentNumber * tempNumber);
        dfs(N, number, count + 1 + i, currentNumber / tempNumber);
    }
}
 
int solution(int N, int number) {
    dfs(N, number, 0, 0);
    //answer가 9라는 뜻은 number와 맞는 경우가 없었던 것이므로 -1 리턴
    if (answer == 9)    return -1;
    return answer;
}
 
void print(int n, int number, int answer) {
    int t = solution(n, number);
    if (t == answer)        cout << "정답" << endl;
    else        cout << "틀림" << endl;
    ::answer = 9;
}
 
int main() {
    print(5, 12, 4);
    print(2, 11, 3);
    print(5, 31168, -1);
    return 0;
}

---

4. 결과

dfs 풀이시간