[프로그래머스]N으로 표현하기
다시 풀어봤다2
일단 이 문제는 반복되는 subproblem의 형태가 보이므로 동적 계획법을 사용해야 할 것 같다.
N에다가 무슨 연산을 해서 이러쿵 저러쿵 할 것이 아니라, “ number를 k개 사용해서 만들 수 있는 수 를 차례대로 구해나가는 방법 “을 사용해야 할 것 같다. 이것이 가능한 것은 문제에서 k를 8로 제한을 줬기 때문이다.
그럼 동적계획법을 사용하여 어떤 걸 할 수 있나??? → 3개로만들 수 있는 수를 구할 때, 2개로 만들 수 있는 것과 1개로 만들 수 있는 것의 조합으로 → 어떤 것을 만들 수 있다.
- k개의 N을 가지고 만들 수 있는 경우들
1개로 -> 5
2개 -> 55 ,5/5, 5*5, 5+5
3개 -> 555, ( 1개로만들수 있는 +2개로만들) ,( 2개로 만들 수 있는 것, 1개로 만들 수 있는 것 )-
동적 계획법이 되는 이유
- 3 : (2+1)(1+2)
- 4 : (3+1)(2+2)(1+3)
- 5 : (4+1)(3+2)(2+3)(1+4)
이는, k개로 만들었던 세트와 i-k개로 만들었던 세트를 재사용하여 조합한 결과들이다.
다시 풀어봤다 1
이 문제는 전에 풀어봤던 문제임에도 또 다시 풀지 못했다.
(25분고민.. 오늘은 다시 푸는 문제임에도 어려움이 많이 느껴져 길게 고민하기가 힘들었다)
지난번과 비슷한 상태였던 것 같다 . 따라서 다른 사람의 풀이를 빠르게 보았다. 동적 프로그래밍은 항상 새롭고 어렵다.
지난번 처럼 ~~(잘못) 집중하고 집착하던 부분~~은 이런 부분이었다.
- 어떤 수 number을 만들 기 위해서는 , y1 , y2, y3 ... 이런 component들이 필요하고, ~~이 각각을 만드는 최소의 개수를 구해 두고 사용하자~~ (아무튼 동적계획법이 아닐까 ? 라고 생각 하는데, 아주 복잡하고, 심지어는 구하는 법이 있는지도 모르겠는...그런 방법으로만 생각을 하고 있따 )
- 그런데 그렇게 되면, y1, y2,y3에 대해 사칙연산을 하는 방법의 수도 다 고려해야하는데
- 어떻게 푸는거지??????
- 하지만 문제를 풀기 위해서는 반대로 생각해야한다 💥💥...!!
- N을 1번 사용해서 만들 수 있는 수 → N을 2 번 사용해서 만들 수 있는 수 → N을 세 번 사용해서 만들 수 있는 수 ...... 이런식으로
그런데 이 때 , i 번 사용해서 만들 수 있는 수에 대해서는 아래와 같은 규칙이 있다.
- N을 1번 사용해서 만들 수 있는 수
- 1번세트 : 5
- N을 2번 사용해서 만들 수 있는 수
- 2번세트 : (55)(5+5 =10)(5/5 =1 )(5*5 = 25 )(5-5 = 0) =⇒ 55를 제외하고는, 1번세트에 있던 값을 이용하는 모습을 볼 수 있다.
- N을 3번 사용해서 만들 수 있는 수 : 생각해 보면,
- 3번세트: (555)(5 +/- 55)(5 +/- 10 ) (5 +/- 1) (5 +/- 25)(5 +/-* 0)
- 여기서 눈치 챌 수 있는가 ? i 번 사용하여 만들 때에는,
- n을 i번사용한수
- i-k번째 세트와 k번째 세트에서 나오는 수의 연산
import java.util.*;
class Solution {
public StringBuilder sb = new StringBuilder("");
public Set<Integer>[] sets = new Set[9];
public int solution(int N, int number) {
int answer = 0;
// init sets : 각 set[i]는 i+1번째 세트 : i+1개로 만들 수 있는 "숫자"를 뜻한다.
for(int i=0;i<sets.length;i++)
sets[i] = new HashSet<>();
// N을 1번 -> 8번 이용하여만들수 있는 수 중, number와 같은 경우, 즉시 리턴
for(int i=1;i<=8;i++){
// 결국 sb는 하나씩 N을 추가
sb.append(Integer.toString(N));
sets[i].add(Integer.parseInt(sb.toString()));
// NNN...(i개) 이 number와 같은 경우에는 makeSet을 돌지 않도록 shortcut을만들었다
if(sets[i].contains(number)||makeSet(i,number)) {
answer = i;
break;
}
}
if(answer==0) answer =-1;
return answer;
}
// number를 찾게 되면
public boolean makeSet(int i,int number){
int temp =0;
// i-k번째 세트와 k번째 세트를 사용
for(int k=1,c=i-k;k<=i/2;k++,c--){
for(int ke:sets[k]){
for(int ce:sets[c]){
// 4가지 연산 ( 이 때, /와 -의 경우, 순서가 바뀌는 경우도 서로다른 경우다 )
sets[i].add(ke+ce);
sets[i].add(ke*ce);
if(ce!=0)sets[i].add(ke/ce);
if(ke!=0)sets[i].add(ce/ke);
sets[i].add(ke-ce);
sets[i].add(ce-ke);
}
}
if(sets[i].contains(number)) return true;
}
return false;
}
}테스트 1 〉 통과 (1.60ms, 71.3MB)
테스트 2 〉 통과 (0.08ms, 77.3MB)
테스트 3 〉 통과 (0.19ms, 76.2MB)
테스트 4 〉 통과 (23.87ms, 81.2MB)
테스트 5 〉 통과 (10.74ms, 81.8MB)
테스트 6 〉 통과 (0.77ms, 74.7MB)
테스트 7 〉 통과 (0.57ms, 74.3MB)
테스트 8 〉 통과 (5.73ms, 82.5MB)
테스트 9 〉 통과 (0.05ms, 74MB)
- 이런식으로 [ 동적 계획법 ] 문제 중에서는, i-1 번째 에서 나오는 값들(i-1번째 set에 나오는 값들)을 이용한 문제들이 있곤 한 것 같다 . 아주 같진 않지만, 아래의 문제도 비슷한 부분이 있었다.
