DP
N으로 표현
💡 Dynamic Programming
import java.util.*;
class Solution {
public void unionSet(Set<Integer> union, Set<Integer> a, Set<Integer> b) {
for (int n1 : a) {
for (int n2 : b) {
union.add(n1 + n2);
union.add(n1 - n2);
union.add(n1 * n2);
if (n2 != 0)
union.add(n1 / n2);
}
}
}
public int solution(int N, int number) {
List<Set<Integer>> setList = new ArrayList<>();
for (int i = 0; i < 9; i++) {
setList.add(new HashSet<>());
}
setList.get(1).add(N);
if (number == N) return 1;
for (int i = 2; i < 9; i++) {
for (int j = 1; j <= i / 2; j++) {
unionSet(setList.get(i), setList.get(i - j), setList.get(j));
unionSet(setList.get(i), setList.get(j), setList.get(i - j));
}
String n = Integer.toString(N);
setList.get(i).add(Integer.parseInt(n.repeat(i)));
for (int num : setList.get(i)) {
if (num == number) return i;
}
}
return -1;
}
}import java.util.HashSet;
import java.util.Set;
class Solution {
public int solution(int N, int number) {
int answer = -1;
Set<Integer>[] setArr = new Set[9];
int t = N;
for(int i = 1; i < 9; i++) {
setArr[i] = new HashSet<>();
setArr[i].add(t);
t = t * 10 + N;
}
for(int i = 1; i < 9; i++) {
for(int j = 1; j < i; j++) {
for(Integer a : setArr[j]) {
for(Integer b : setArr[i - j]) {
setArr[i].add(a + b);
setArr[i].add(a - b);
setArr[i].add(b - a);
setArr[i].add(a * b);
if(b != 0) {
setArr[i].add(a / b);
}
if(a != 0) {
setArr[i].add(b / a);
}
}
}
}
}
for(int i = 1; i < 9; i++) {
if(setArr[i].contains(number)) {
answer = i;
break;
}
}
return answer;
}
}import java.util.*;
class Solution {
public int solution(int N, int number) {
List<Set<Integer>> countList = new ArrayList<>();
for(int i=0; i<9; i++)
countList.add(new HashSet<>());
countList.get(1).add(N);
for(int i=2; i<9; i++){
Set<Integer> countSet = countList.get(i);
for(int j=1; j<=i; j++){
Set<Integer> preSet = countList.get(j);
Set<Integer> postSet = countList.get(i - j);
for(int preNum : preSet){
for(int postNum : postSet){
countSet.add(preNum + postNum);
countSet.add(preNum - postNum);
countSet.add(preNum * postNum);
if(preNum != 0 && postNum != 0)
countSet.add(preNum / postNum);
}
}
}
countSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
}
for(Set<Integer> sub : countList){
if(sub.contains(number))
return countList.indexOf(sub);
}
return -1;
}
}💡 Depth First Search
class Solution {
int answer = -1;
public int solution(int N, int number) {
dfs(N, 0, 0, number, "");
return answer;
}
public void dfs(int n, int pos, int num, int number, String s) {
if (pos > 8)
return;
if (num == number) {
if (pos < answer || answer == -1) {
System.out.println(s);
answer = pos;
}
return;
}
int nn=0;
for (int i = 0; i < 8; i++) {
nn=nn*10+n;
dfs(n, pos + 1+i, num + nn, number, s + "+");
dfs(n, pos + 1+i, num - nn, number, s + "-");
dfs(n, pos + 1+i, num * nn, number, s + "*");
dfs(n, pos + 1+i, num / nn, number, s + "/");
}
// dfs(n,pos+1,num*10+n,number,s+"5");
}
}import java.util.*;
class Solution {
static int min = Integer.MAX_VALUE;
public int solution(int N, int number) {
dfs(0, N, number, 0);
if (min == Integer.MAX_VALUE) return -1;
return min;
}
public void dfs(int depth, int N, int number, int current) {
if (depth > 8) {
return;
}
if (number == current) {
min = Math.min(depth, min);
return;
}
int temp = 0;
for (int i = 0; i < 8; i++) {
if (depth + i < 8) {
temp = temp * 10 + N;
dfs(depth + i + 1, N, number, current + temp);
dfs(depth + i + 1, N, number, current - temp);
dfs(depth + i + 1, N, number, current / temp);
dfs(depth + i + 1, N, number, current * temp);
}
}
}
}정수 삼각형
class Solution {
public int solution(int[][] triangle) {
int[][] dp = new int[triangle.length][triangle.length];
dp[0][0] = triangle[0][0];
for (int i = 1; i < triangle.length; i++) {
dp[i][0] = dp[i - 1][0] + triangle[i][0];
for (int j = 1; j <= i; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
}
int answer = 0;
for (int i = 0; i < triangle.length; i++) {
answer = Math.max(answer, dp[triangle.length - 1][i]);
}
return answer;
}
} 등굣길
import java.util.*;
class Solution {
public int solution(int m, int n, int[][] puddles) {
int mod = 1000000007;
int[][] board = new int[n + 1][m + 1];
for(int i = 0; i < puddles.length; i++) {
board[puddles[i][1]][puddles[i][0]] = -1;
}
board[1][1] = 1;
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < m + 1; j++) {
if(board[i][j] == -1) continue;
if(board[i - 1][j] > 0) board[i][j] += board[i - 1][j] % mod;
if(board[i][j - 1] > 0) board[i][j] += board[i][j - 1] % mod;
}
}
return board[n][m] % mod;
}
} 사칙연산
도둑질
import java.util.*;
class Solution {
public int solution(int[] money) {
int[] dpf = new int[money.length];
int[] dps = new int[money.length];
for (int i = 0; i < money.length; i ++) {
dpf[i] = money[i];
dps[i] = money[i];
}
dpf[1] = -1;
dps[0] = -1;
dpf[2] += dpf[0];
for (int i = 3; i < money.length; i++) {
dpf[i] += Math.max(dpf[i - 2], dpf[i - 3]);
dps[i] += Math.max(dps[i - 2], dps[i - 3]);
}
int f = Math.max(dpf[money.length - 2], dpf[money.length - 3]);
int s = Math.max(dps[money.length - 1], dps[money.length -2]);
return Math.max(f, s);
}
}Last updated