프로그래머스 N으로 표현

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42895?language=cpp 

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

 

문제접근법 : 모든경우의 수를 다구해도 괜찮습니다.

현재를 0으로 시작해서 0+n,0-n,0*n,0/n 이것을 n을 한번쓴경우

2번썼을때 0+nn,0-nn,0*nn,0/nn 이런식으로 그값들을 저장하면서

8개까지 사용한것들의 모든결과값들에 number가 되는지 확인하여 가장 최소값을 구합니다.

 

 

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <bits/stdc++.h> using namespace std; #define ll long long   int res = 1e8; void backtrack(int n, int number, int cur=0, int height=0) {     if (height > 8)return;     if (cur == number) {         res = min(res, height);         return;     }     int temp = 0;     for (int i = 1; i + height < 9; i++) {         temp = temp * 10 + n;         backtrack(n, number, cur + temp, i + height);         backtrack(n, number, cur - temp, i + height);         backtrack(n, number, cur * temp, i + height);         backtrack(n, number, cur / temp, i + height);     }   }   int solution(int N, int number) {     int answer = 1e8;     backtrack(N, number);       return res == 1e8 ? -1 : res; } Colored by Color Scripter

cs

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.