[programmers] Lv.3 N으로 표현(c++)

이 문제는 DP 문제이다.

(DP 링크 추가 예정...)

 

#include <string>
#include <vector>
#include <set>

using namespace std;

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

int solution(int N, int number) {
    vector<set<int>> dp(9);
   
    for(int i=1; i<=8; i++){
        dp[i].insert(nnn(N, i)); // 숫자 i개 사용
        
        for(int x=1; x<=i; x++){
            for(int y=1; y<=i; y++){
                if(x+y > 8) break;
                
                for(int a: dp[x]){
                    for(int b: dp[y]){
                        if(a+b <= 32000) dp[x+y].insert(a+b);
                        if(a-b >= 1) dp[x+y].insert(a-b);
                        if(a*b <= 32000) dp[x+y].insert(a*b);
                        if(a/b >= 1) dp[x+y].insert(a/b);
                    }
                }
            }
        }
        for(int a: dp[i]){
            if(a == number) return i;
        }
    }
    return -1;
}

---

문제

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

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

728x90

---

[접근1]

숫자 N에 대하여 NNN....(num개)을 만들어줄 함수 생성

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

---

[접근2]

dp vector를만들어준다.

i번째 원소는 N을 i개 사용하여 만들 수 있는 숫자를 가지고 있다.

기본적으로 NNN.....(i개)를 포함하고있다.

vector<set<int>> dp(9);
   
for(int i=1; i<=8; i++){
    dp[i].insert(nnn(N, i)); // 숫자 i개 사용

    ...
}

---

[접근3]

1부터 i개 사용하여 만든 값들을 연산하여 새로운 값을 만들어낸다.

새로 만든 값의 N 사용 횟수는 8을 넘으면 안되며, 그 값은 1이상 32000 이하이다.

for(int i=1; i<=8; i++){
    ...
    
    for(int x=1; x<=i; x++){
        for(int y=1; y<=i; y++){
            if(x+y > 8) break;

            for(int a: dp[x]){
                for(int b: dp[y]){
                    if(a+b <= 32000) dp[x+y].insert(a+b);
                    if(a-b >= 1) dp[x+y].insert(a-b);
                    if(a*b <= 32000) dp[x+y].insert(a*b);
                    if(a/b >= 1) dp[x+y].insert(a/b);
                }
            }
        }
    }
    ...
}

---

[접근4]

N을 i개 사용한것에 대하여 앞 과정을 끝내면 i개 사용하여 구한 값들은 다 구해진것이다.

따라서 dp[i]의 값들 중 원하는 값이 있는지 확인하고, 있으면 바로 return한다.

N을 8까지 사용했는데도 원하는 값이 나오지 않았다면 -1을 return한다.

for(int i=1; i<=8; i++){
    ...
    
    for(int a: dp[i]){
        if(a == number) return i;
    }
}
return -1;