본문 바로가기
알고리즘

[SW Expert Academy] 숫자만들기

by minkang 2021. 4. 16.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

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의 인덱스를 인수로 받는 재귀함수를 이용해서 풀었습니다.