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

 

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

 

programmers.co.kr

 

 

** 메모이제이션

이전에 계산한 값을 저장해놓고 계속 활용

 

v[0]~v[8]까지 N, NN, NNN 의 값을 먼저 저장

v[0]의 경우 N 한가지 경우밖에 없음

v[1]의 경우 NN, N+N, N*N, N-N, N/N 5가지 경우

NN

iterator ii:: v[0].begin()~v[0].end()

   it + iterator ji:: v[0].begin()~v[0].end()

   it * iterator ji:: v[0].begin()~v[0].end()

   it - iterator ji:: v[0].begin()~v[0].end()

   it / iterator ji:: v[0].begin()~v[0].end()

 

v[2]의 경우 NNN, NN+N, NN*N, NN-N, NN/N, N+N+N, N+N*N.......

 

v[1]를 계산하는 경우 v[0]의 값을 활용

v[2]를 계산하는 경우 v[1], v[0]의 값을 활용

v[3]을 계산하는 경우 v[2], v[1], v[0]의 값을 활용

v[k]를 계산하는 경우 v[i-1], v[i-2], v[i-3]...v[k-(j-1)]...v[0] 의 값을 활용

 

v[k]의 값 삽입이 끝난 후 

v[0]~v[k]까지의 값들을 한번 검색하여 number가 있다면 해당 k+1의 값이 answer로 출력(인덱스 0부터 시작하기 때문)

없다면 개수가 8개보다 큰 경우이기 때문에 -1 출력

 

int solution(int N, int number) {
	int answer = -1;
	vector<set<int>> v(8);
	int sum=0;
	// v[0]~v[8]까지 N, NN, NNN, NNNN... 값 저장
	for (int i = 0;i < 8;i++) {
		sum = 10 * sum +N;
		v[i].insert(sum);
    }
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < i; j++) {
			for (auto &ii : v[j]) {
				for (auto &ji : v[i-j-1]) {
					v[i].insert(ii + ji);
					v[i].insert(ii * ji);
					if(ii-ji>0)
						v[i].insert(ii - ji);
					if(ii/ji >0)
						v[i].insert(ii / ji);
				}
			}
		}
		if (v[i].find(number) != v[i].end()) 
			return i + 1;
	}
	return answer;
}

+ Recent posts