SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
package SW.알고리즘;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 숫자만들기 {
static int operator[];
static int nums[];
static int N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
operator = new int[4];
for(int test_case = 1; test_case<=T; test_case++) {
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<4; i++) {
operator[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
nums = new int[N];
for(int i=0; i<N; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
for(int i=0; i<4; i++) {
if(operator[i] != 0) {
operator[i]--;
dfs(nums[0], nums[1], i, 1);
operator[i]++;
}
}
System.out.println("#"+test_case + " " + (max-min));
}
}
static int min;
static int max;
private static void dfs(int prev, int next, int i, int curIdx) {
if(i == 0) { // +
next = prev + next;
}
else if(i == 1) { // -
next = prev - next;
}
else if(i == 2) { // *
next = prev * next;
}
else if(i == 3) { // /
next = prev / next;
}
for(int k=0; k<4; k++) {
if(operator[k] != 0) {
operator[k]--;
dfs(next, nums[curIdx+1], k, curIdx+1);
operator[k]++;
}
}
if(curIdx == N-1) {
max = Math.max(next, max);
min = Math.min(next, min);
return;
}
}
}
소요시간 : 40분
프로젝트에 몰두하다 코딩테스트를 위해 다시 알고리즘 공부를 하고 있습니다.
풀었었던 문제지만 너무 오랜만이라 새로 푸는 기분이네요 ㅎㅎ.. 다시 화이팅!!
숫자 만들기는 가능한 모든 연산을 하고 그 중 최댓값-최솟값을 해야합니다.
따라서 완전탐색의 문제였습니다.
이전값, 다음값, 선택된 연산자인덱스, 현재 nums의 인덱스를 인수로 받는 재귀함수를 이용해서 풀었습니다.
'알고리즘' 카테고리의 다른 글
[SW Expert Academy] 특이한 자석 - java (0) | 2021.04.17 |
---|---|
[SW Expert Academy] 요리사 (0) | 2021.04.16 |
[프로그래머스] 게임 맵 최단거리 - lv2 (1) | 2021.03.17 |
[프로그래머스] 합승택시요금 (lv3) (0) | 2021.02.22 |
[프로그래머스] 스킬트리 - lv2 (1) | 2021.01.21 |