12) 프로그래머스 Lv3 - N으로 표현

코딩테스트 연습 - N으로 표현 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

SET 활용이 미숙해서 헤맴 + 아이디어가 떠오르지 않음 이었다....

#include <bits/stdc++.h>

using namespace std;

int DP[9];

int solution(int N, int number) {
    int answer = -1;
    
    fill_n(DP, 9, 0);
    
    set<int> DP[9];
    set<int>::iterator iter_find;
    set<int>::iterator iter_begin;
    set<int>::iterator iter_end;
    
    if(N == number) {
        return 1;
    }
    for(int i = 1; i < 9; i++) {
        int j = 0;
        int tmp = 0;
        while(j != i) {
            tmp = tmp * 10 + N;
            j++;
        }
        
        DP[i].insert(tmp);
        for(j = 1; j < i; j++) {
            for(iter_begin = DP[j].begin(); iter_begin != DP[j].end(); iter_begin++) {
                for(iter_end = DP[i-j].begin(); iter_end != DP[i-j].end(); iter_end++) {
                    DP[i].insert(*iter_begin+(*iter_end));
                    if(*iter_begin-(*iter_end) >= 0)
                        DP[i].insert(*iter_begin-(*iter_end));
                    if(*iter_end != 0)
                        DP[i].insert(*iter_begin/(*iter_end));
                    DP[i].insert(*iter_begin*(*iter_end));
                }
            }
        }
        if(*DP[i].find(number) == number)
            return i;
    }
    
    
    
    return answer;
}

생각해내면 그렇게 어려운 문제는 아니었던것 같지만 아이디어 떠올리기가 너무 어려웠던 문제....

 

다음과 같은 방법으로 문제를 풀었다... (🖩 : +, -, *, / | NN : 연속된 수 (ex. 333 (N = 3))

 

DP[1] = N

DP[2] = NN, DP[1] 🖩 DP[1]

DP[3] = NNN, DP[1] 🖩 DP[2], DP[2] 🖩 DP[1]

DP[4] = NNNN, DP[1] 🖩 DP[3], DP[2] 🖩 DP[2], DP[3] 🖩 DP[1]

.....

로 점화식을 활용해서 구했다.

 

점화식 계산 한번 끝날때 마다 number가 있는지 체크를 해줬다.

 

※ 주의

뺄셈의 경우에는 굳이 음수까지 체크할 필요는 없다. - 곱셈, 나눗셈을 해도 음수는 음수.

나눗셈 ( / )의 경우에는 0으로 나뉘지 않았는지 확인하자.

 

SET의 경우에는 정리 할 필요성을 느꼈다....

그리고 DP 어려웡....ㅠㅠㅠㅠ