[프로그래머스] 동적 계획법 - N으로 표현

...

처음에는 각각의 수에 대해 몇개의 N으로 표현가능한가 점화식도 세워보고..

규칙성도 찾으려 했으나.. 너무 어려워서 포기

 

그래서 결국 풀이를 서칭해봤다.

핵심은 i개의 N으로 표현 가능한 수들을 찾고 number가 그 안에 포함되어있는 지를 체크하는 거였다.

 

참고 : https://dheldh77.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84

[프로그래머스] N으로 표현

 

흑흑 글만 읽고 코드는 내가 짜보려고 했으나

op2를 구하는 것에 어려움을 느꼈고 결국 포기.. ㅎㅎ

 

import java.util.*;

class Solution {
    public int solution(int N, int number) {        
        int answer = -1;
        
        ArrayList<Integer> list=new ArrayList<>();
        String temp="";
        String n=Integer.toString(N);
        
        
        for(int i=1;i<=8;i++) {
        	int size=list.size();
        	for(int j=0;j<size;j++) {
        		int k=list.get(j);
        		if(!list.contains(k+N))list.add(k+N);
        		if(!list.contains(k*N))list.add(k*N);
        		if(k!=0 && !list.contains(k/N))list.add(k/N);
        		if(k!=0 && !list.contains(N/k))list.add(N/k);
        	}
        	temp+=n;
        	list.add(Integer.parseInt(temp));
        	if(list.contains(number)) return answer=i;
        }
        
        return answer;
    }
}

이건 내가 짰던 코드인데 

현재 배열에 대해 N과 사칙연산 한 것을 더해주면서 반복문을 돈다.

 

즉 4개의 N을 가지고 수를 만들 때 나는 "(3개의 N으로 만들수 있는 수) *+/- (N)"의 결과값들만 list에 포함한 것이다.

"(2개의 N으로 만들 수 있는 수) *+/- (2개의 N으로 만들 수 있는 수)" 이것도 포함해 줬어야 했는데 ㅠㅠ

이과정이 복잡해서 결국 정답코드를 봤다..

 

public static int solution(int n, int num) {
		int ans = 0;
		ArrayList <HashSet<Integer>> list = new ArrayList<>();
		HashSet <Integer> set = new HashSet<>();
		set.add(n);
		list.add(set);
		
		while(ans < 8) {
			if(list.get(ans).contains(num)) break;
			ans++;
			
			HashSet <Integer> nset = new HashSet<>();
			String s = "";
			for(int i = 0; i < ans + 1; i++) s += String.valueOf(n);
			nset.add(Integer.parseInt(s));
			
			for(int i = 0; i <= ans / 2; i++) {
				for(int j = 0; i + j < ans; j++) {
					for(Iterator it1 = list.get(i).iterator(); it1.hasNext();) {
						int op1 = (int)it1.next();
						for(Iterator it2 = list.get(j).iterator(); it2.hasNext();) {
							int op2 = (int)it2.next();
							nset.add(op1 + op2);
							nset.add(op1 - op2);
							nset.add(op1 * op2);
							if(op2 != 0) nset.add(op1 / op2);
						}
					}
				}
			}
			list.add(nset);
		}
		
		return (ans >= 8) ? -1 : ans + 1;
	}

참고 블로그에서 가져온 정답 코드이다.

 

이 문제가 동적계획법인 이유는 이전의 결과값들을 저장해서 사용해서 일까..? 

흠.. 이문제를 완전탐색을 이용해서 푼 사람들도 많았다.