[Lv.2] 타겟 넘버 : Java

프로그래머스

 

class Solution { 
    static int target; 
    static int cnt = 0; 
    public int solution(int[] numbers, int target) { 
        // DFS, 백트래킹 > 만들 수 있는 숫자 다 만들어보기 > target이랑 일치하면 카운트 
        this.target = target; 
        dfs(numbers,0, 0); 
        return cnt;
    } 
    
    public static void dfs(int[] numbers, int idx, int sum){ 
        if(idx == numbers.length) {
            // 모든 숫자 사용한 경우
            if(sum == target){
                cnt++;
            }
            return;
        }
         
        dfs(numbers, idx+1, sum-numbers[idx]);
        dfs(numbers, idx+1, sum+numbers[idx]);
    } 
}

---

모음 사전은 모음을 모두 사용하지 않아도 타겟 단어 찾을 수 있음 > 조기 종료 조건 작성하기

타겟 넘버는 주어진 숫자를 다 사용해서 타겟 넘버를 찾는 거임 > 조기 종료 조건X, 주어진 숫자 다 사용하는게 종료 조건

[Lv.2] 모음 사전 : Java

 

'피로도' 문제에서는 for문 사용하고 '타겟 넘버'에서는 사용 안하는 이유

>타겟 넘버는 사용할 numbers의 순서 정해져 있음 => 정해야 하는 건 +/- 선택뿐

>던전은 순서 정해져 있지 않음 =>for문으로 모든 후보 탐색

https://say021.tistory.com/180