494. Target Sum

https://leetcode.com/problems/target-sum/description/?envType=daily-question&envId=2025-01-04

 

You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.

 

nums[i]의 원소들을 가지고 +, -를 사용하여 target이 되는 경우의 수를 구하는 문제였다. 

nums의 길이 제한도 20이라 백트래킹 방식의 풀이를 떠올렸다. 

 

기존 풀이

public void dfs(int [] nums, int depth, int cur, int target) {
    if (depth == nums.length - 1) {
        res++;
        return;
    }

    for(int i = 0; i < nums.length; i++) {
        if (!visited[i]){
            visited[i] = true;
            dfs(nums, i, cur + nums[i], target);
            dfs(nums, i, cur - nums[i], target);
            visited[i] = false;
        }
    }
}

 

우선, cur 값이 target이 되어야 res를 증가시켜줘야 하는데 해당 조건이 누락되었고 불필요한 루프를 사용하면서 depth는 사용하지도 않았다.

아직 백트래킹 개념이 헷갈리는것 같다 ㅠ

 

 

 

답

class Solution {
    int res = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, 0, 0, target);
        return res;
    }

    public void dfs(int [] nums, int depth, int cur, int target) {
        if (depth == nums.length) {
            if (cur == target) {
                res++;
            }
            return;
        }

        dfs(nums, depth + 1, cur + nums[depth], target);
        dfs(nums, depth + 1, cur - nums[depth], target);
    }
}

 

이렇게 배열의 끝에 도달했을 때 target과 같을 때만 res를 증가시켜주고,

for문을 사용하여 순회할 필요 없이 depth 값만 사용하여 전진시켜주면 되는 문제였다. 

 

https://www.acmicpc.net/problem/14888

 

이 백준 문제가 똑같은 방식으로 풀 수 있다.

public class boj14888 {
    static int n;
    static int [] cal = new int[4];
    static int [] arr;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        // +, -, x, /
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++){
            cal[i] = Integer.parseInt(st.nextToken());
        }

        dfs(1, arr[0]); // 초기값을 저장
        System.out.println(max);
        System.out.println(min);
    }

    public static void dfs(int depth, int cur) {
        if (depth == n) {
            max = Math.max(cur, max);
            min = Math.min(cur, min);
            return;
        }

        for(int i = 0; i < 4; i++) {
            if (cal[i] > 0) {
                cal[i]--;
                if (i == 0) {
                    dfs(depth + 1, cur + arr[depth]);
                }
                else if (i == 1) {
                    dfs(depth + 1, cur - arr[depth]);
                }
                else if (i == 2) {
                    dfs(depth + 1, cur * arr[depth]);
                }
                else if (i == 3) {
                    dfs(depth + 1, cur / arr[depth]);
                }
                cal[i]++;
            }
        }
    }
}

 

백준 문제는 한번에 풀었다!