N으로 표현+STL(set, unordered set)

• 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번만 사용하여 표현할 수 있습니다.

출처

Polish Olympiad in Informatics

 

우선 문제 풀이 로직부터 설명.

N이 있으면

N이 1개 있을때 만들 수 있는 수들의 조합

N이 2개 있을때 만들 수 있는 수들의 조합

. . .

N이 8개 있을때 만들 수 있는 수들의 조합을 bottom-up방식으로 만들어간다.

 

처음에 벡터로 해볼려고 했는데 자꾸 coredump에러가 나서 이유는 찾지 못했고 로직 맞췄으니 그냥 답을 보겠다는 합리화를 거쳤다.

그래서 코드는 

#include <vector> 
#include <unordered_set> 
#include <iostream>
using namespace std;

int get_Ns(int N, int idx) {
    int result = N;
    for (int i = 1; i <= idx; i++) {
        result = result * 10 + N;
    }
    return result;
}

int solution(int N, int number) {
    if (N == number) return 1;  
    vector< unordered_set<int> > DP(8);

    DP[0].insert(N); 

    for (int k = 1; k < 8; k++) {
        DP[k].insert(get_Ns(N, k));
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (i + j + 1 != k) continue;
                for (int a : DP[i]) {
                    for (int b : DP[j]) {
                        DP[k].insert(a + b);
                        if (a - b > 0)
                            DP[k].insert(a - b);
                        DP[k].insert(a * b);
                        if (a / b > 0) DP[k].insert(a / b);
                    }
                }
            }
        }
        if (DP[k].find(number) != DP[k].end()) 
            return k + 1;
    }
    return -1;
}

이렇게 돌아간다 . 여기서 set과 unordered set을 알아야되는데 지금부터 정리르 한번 해보겠다. 

우선 

set

set container라고하며 노드 기반 컨테이너이며 균형 이진트리로 되어있단다. 

그리고 key 값은 중복되지 않으며 삽입시 자동으로 정렬해주는 좋은 기능이 있다. 디폴트는 오름차순인가보다.

 

set을 그럼 어떻게 쓰냐 #include <set>헤더파일안에 들어있단다...set<int> s;set<pair<int,string>> s2;

방식이 유사하다 벡터와

 

또 하나 set<int> s2(s1);이렇게 쓰면 s1을 복사한 s2가 된단다. 이것도 신기하다.

s.begin(),s.end()벡터랑 비슷하다 또 한가지 신기한 점은

s.rbegin(),s.rend()

리버스로 리턴이 가능하단다 ㅋㅋ

for(iter = s.rbegin(); iter != s.rend(); iter++){

    cout << * iter << endl;

}

예시는 요렇게...

s.count(원소 k); 원소 k의 갯수를 반환한다.

s.insert(원소 k); 원소 k를 삽입한다.

s.insert(iter,k) k를 이터레이터가 가르키는 위치 부터 삽입한다.

  set<int> s;

 

    s.insert(40);    

    s.insert(10);

    s.insert(80);

    s.insert(30);

    s.insert(70);

    s.insert(60);

    s.insert(20);

    s.insert(50);

 

    set<int>::iterator iter;

    for(iter = s.begin(); iter != s.end(); iter++){

        cout << *iter << " " ;

    }

    cout << endl;

그럼 이제 unordered_set은 뭘까

unordered_set은 말 그대로 정렬안된 셋이다. 하지만 중복은 없다.

 

그래서#include <unordered_set>헤더에서 받아와서

<unordered_set> US처럼 선언하고 사용하면 되는데 

정렬이 되지않으니 말그대로 정렬되지 않는다 ㅋ_ㅋ (말장난 아님) 여기까지 읽어줬다면 

당신은 이 블로그 찐팬이 틀림없다..

찐팬들은 댓글 달아주시면 내가 그 사람 잘되라고 기도하겠다.