[프로그래머스] N으로 표현(Level 3)

📝문제 링크

프로그래머스 > 동적계획법 > N으로 표현 문제보기

🔑문제 KeyPoint

사실 DP문제는 너무 어렵다,,,
내 머리로는 풀이가 도저히 불가능하여, 해당 블로그 내용을 참조. -> 참조블로그

DP문제에 대한 접근법이 자세하게 나와있는 내용도 참고하면 좋을것 같다. 온코더 DP문제(Knapsack) 풀이

DP의 계산식을 세워라‼
dp[n] = dp[n-i]+dp[i]

✔ DP문제는 0~N번까지의 계산을 차근차근 생각해보자.

N 1번 이용 ,
-> 무조건 1자리수
N 2번 이용,
-> N (+, -, *, /) N -> N과 N을 사칙연산하거나
-> NN (+, -, *, /) N -> N을 2번이어붙여서 만든 값과 N을 사칙연산한 경우
...

반복하여 최대 8번까지

💻문제 풀이

우선, 사용횟수가 8번이 넘으면 -1을 리턴,
그리고 N은 1부터 9까지만 주어진다는 점을 고려하여 TreeSet[10]의 크기 선언

public int solution(int N, int number) {
	_N = N;
	dynamic = new TreeSet[10];			// N을 최대 9번 곱해봣자 NNNNNNNNN이하의 결과가 나오기 때문에 10으로 크기 설정

	if(N == number) {					// N과 number가 같은경우 무조건 return 1
		return 1;
	}

	for(int i =0;i<=8;i++) {			// N을 사용하는 횟수가 8보다 크면 -1이므로
		solve(i);

		// 연산결과 number와 값이 일치하면 return
		if(dynamic[i].contains(number)) {
			return i;
		}
	}
	return -1;
}
	
public TreeSet<Integer> solve(int n) {
	if((dynamic[n]!= null) && !dynamic[n].isEmpty()) {		// 이미 존재하는 값인 판단하여, 존재하면 return
		return dynamic[n];
	}
		
	// N을 이어서 붙인 NN...N 값 만들기
	int numN=0;
	for(int i=0;i<n;i++) {		
		numN = (10*numN) + _N;
	}
		
	TreeSet<Integer> temp = new TreeSet<>();
	temp.add(numN);			// temp에 numN값 담기
		
		
	// d[n] = d[n-i] + d[i]
	for(int i=1;i<n;i++) {
		int j=n-i;
		TreeSet<Integer> from = solve(i);		// i 번째까지 구한 집합
		TreeSet<Integer> to = solve(j);			// j 번째까지 구한 집합
			
		for(int n1:from) {
			for(int n2:to) {			
				temp.add(n1+n2);
				temp.add(n1-n2);
				temp.add(n1*n2);
				if(n2 !=0) temp.add(n1/n2);
			}
		}
	}
	return dynamic[n] = temp;
}

전체 소스 보기(git)