코딩테스트 -- N으로 표현 (프로그래머스 / c++)

 

코딩테스트 연습 - N으로 표현

 

문제 설명

---

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

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

입출력 예Nnumberreturn

5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

---

문제 내용은 임의숫자 N을 가지고 사칙연산과 반복된수들을 사용해서

number을 만드는데 사용되는 최소 N의 개수를 구하는 문제!

 

일단 오답부터....

처음에는 N을 하나씩 늘려주며 구할려고 했는데

 

**오답...

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

using namespace std;


vector<int>memo;
vector<int>answerlist;

int solution(int N, int number) {
    int answer = 0;
    
    if(number==N){//1
        return 1;
    }
    
    memo.push_back(1);// /
    string count="11";
    memo.push_back(stoi(count)*N);
 
    memo.push_back(2*N);// +
    memo.push_back(0);// -
    memo.push_back(N*N);// *
    
    for(int j=0;j<memo.size();j++){
            cout<<memo[j]<<",";
        }
        
        cout<<"|"<<endl;
    
    for(int i=0;i<6;i++){
        count+="1";
        
        for(int j=0;j<memo.size();j++){
            if(memo[j]==number){
                return i+2;
            }
            answerlist.push_back(N+memo[j]);// +
            if(memo[j]>=N){
                answerlist.push_back(memo[j]-N);// -
            }
            else{
                answerlist.push_back(N-memo[j]);// -
                
            }
            if(memo[j]!=0){
                answerlist.push_back(N/memo[j]);// /
            }
            answerlist.push_back(memo[j]/N);// /
            answerlist.push_back(N*memo[j]);// *
        }
        
        answerlist.push_back(stoi(count)*N);
        
        
        for(int j=0;j<answerlist.size();j++){
            
            memo.push_back(answerlist[j]);
            
        }
        
        sort(memo.begin(), memo.end());
        memo.erase(unique(memo.begin(),memo.end()),memo.end());
        for(int j=0;j<memo.size();j++){
            cout<<memo[j]<<",";
        }
        
        cout<<"|"<<endl;
    }
    
    return -1;
}

이렇게 구하게되면 

solution(8, 53)의 최소 개수식인  8*8 - 88/8 은 구할수가 없더라구요

 

(88/8을 계산 하고 넣어 줘야 하기에)

 

그래서 방법을 하나씩 늘려주는것이 아닌 개수의 조합으로 구하는 것으로 변경해보았습니다.

 

이제 진짜 시작!

---

조합으로 구한다는것은 N의 갯수 (1, 0), (1,1), (2,1), (1,2), (2,2), (3,1), (1,3).... 등등 처럼

개수별로 값을 리스트에 따로 저장하고 불러와 조합하는 방식!

 

이제 구상을 끝났고 정리해보면

1. 개수별 리스트 만들기

2. 조합(개수의 합  8이하까지만 조합)

3. number판별 후 발견하면 정지

 

하면 될 것 같네요

 

먼저 2차원 벡터를 선언해줍시다.

int solution(int N, int number) {
	if (N == number)
		return 1;

	vector<vector<int>> numlist(8);

 

 

그리고 numlist[0](N 1개사용), numlist[1](N 2개사용)..... 이렇게 생각한후 하나씩 조합을 통해 만들어줍시다.

    numlist[0].push_back(N);
    string count="1";// 5, 55 , 555 등을 처리해줄 string
	for (int k = 1; k < 8; k++) {//몇개를 쓸건지
        count+="1";
		for (int i = 0; i < k; i++) {// A개 사용
            
				for (int a : numlist[i]) {
					for (int b : numlist[k-i-1]) {// B개= k-i-1
                        
						numlist[k].push_back(a + b);// +
                        
						if (a - b > 0){
                            numlist[k].push_back(a - b);// -
                        }
                        
						numlist[k].push_back(a * b);// *
						if (a / b > 0){
                            numlist[k].push_back(a / b);// %
                        }
							
					}
				}
			
		}

 

마지막으로 추가된 요소들의 중복요소를 제거해주고 정렬해준뒤 답이 있는지 탐색!

	   numlist[k].push_back(stoi(count)*N);// 5, 55 , 555 등을 추가

		
        sort(numlist[k].begin(), numlist[k].end());
        numlist[k].erase(unique(numlist[k].begin(),numlist[k].end()),numlist[k].end());
        
        for (int a : numlist[k]){
            if(a==number){
                return k+1;
            }

 

여기까지가 끝!

 

**all

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;


int solution(int N, int number) {
	if (N == number)
		return 1;

	vector<vector<int>> numlist(8);
    
	numlist[0].push_back(N);
    string count="1";
	for (int k = 1; k < 8; k++) {//몇개를 쓸건지
        count+="1";
		for (int i = 0; i < k; i++) {// A개 사용
            
				for (int a : numlist[i]) {
					for (int b : numlist[k-i-1]) {// B개= k-i-1
                        
						numlist[k].push_back(a + b);// +
                        
						if (a - b > 0){
                            numlist[k].push_back(a - b);// -
                        }
                        
						numlist[k].push_back(a * b);// *
						if (a / b > 0){
                            numlist[k].push_back(a / b);// %
                        }
							
					}
				}
			
		}
        
		numlist[k].push_back(stoi(count)*N);

		
        sort(numlist[k].begin(), numlist[k].end());
        numlist[k].erase(unique(numlist[k].begin(),numlist[k].end()),numlist[k].end());
        
        for (int a : numlist[k]){
            if(a==number){
                return k+1;
            }
        }
	}

	return -1;
}

 

 

 

틀린 점이 있다면 댓 달아주세요!