https://www.acmicpc.net/problem/18111
문제
> 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
> 5를 사용한 횟수는 각각 6,5,4 입니다.
> 그리고 이중 가장 작은 경우는 4입니다.
> 이처럼 숫자 N과 number가 주어질 때,
N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.접근
dp를 사용하는데 이때, dp의 인덱스 기준을 해당 N을 사용한 횟수로 두고 가야한다.
그리고 이 dp(i)에 대한 원소들은 N을 i번 썼을 때, 만들 수 있는 수들을 가진다.
또 모든 경우를 따지다 보면 겹치는 수가 많기 때문에 Set을 사용하여 겹치는 수를 처리한다.
8보다 크면 -1을 출력하므로 8까지의 모든 경우를 구한뒤 1부터 8까지 contains로 원하는 number을 찾으면 해당 i를 출력한다.
문제해결
> dp를 동적배열로 선언하는데 겹치는 수의 처리를 위해 Integer형 Set타입으로 선언한다.
> 초기 설정으로 각 dp인덱스에 Set을 생성해주고 i에 따라 5, 55, 555...를 위해 초기값으로 넣어준다.
> 이제 2부터 8까지의 경우를 구해주기 위해 반복한다.
> 내부에서 1부터 i-1까지 반복을 하며 해당 i의 경우를 위한 모든 경우를 따져준다.
> 예를들어 i가 4라면 t가 1,2,3이고 이에따라 dp(1)과 dp(3), dp(2)와 do(2), dp(3)과 dp(1)로 dp(4)의 경우를 생성한다.
> 경우는 사칙연산으로 만드는데 나누기 연산은 zerodivision문제를 방지하기위해 이를 처리한다.
> 모든 경우를 구했으므로 1부터 8까지 dp를 돌며 해당 i번 째에 원하는 number가 있는지 contains로 확인한다.
> 있다면 i를 반환하고 끝내며, 없으면 8을 넘어가므로 -1을 반환한다.코드
import java.util.*;
import java.lang.*;
class Solution {
public int solution(int N, int number) {
List<Set<Integer>> dp = new ArrayList<>();
for(int i = 0; i < 9; i++) {
dp.add(new HashSet<>());
if(i < 1) continue;
int tmp = N;
for(int t = 0; t < i-1; t++) tmp = tmp * 10 + N;
dp.get(i).add(tmp);
}
for(int i = 2; i < 9; i++) {
for(int t = 1; t <= i-1; t++) {
Set<Integer> a = dp.get(t);
Set<Integer> b = dp.get(i-t);
for(Integer A : a) {
for(Integer B : b) {
dp.get(i).add(A + B);
dp.get(i).add(A - B);
dp.get(i).add(A * B);
if(B != 0) dp.get(i).add(A / B);
}
}
}
}
for(int i = 1; i < 9; i++) {
if(dp.get(i).contains(number)) return i;
}
return -1;
}
}
후기
자료구조를 사용하는 부분이 굉장히 어렸웠고 반복문이 깊어지며 헷갈려서 힘들었다.
