[프로그래머스] 타겟 넘버

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

코드

package Programmers.Level2;

public class TargetNumber {
	
	private static int targetNum ;

	public static void main(String[] args) {
		
		int[] numbers = { 1,1,1,1,1 } ;
		
		int target = 3;
		
		int answer = solution(numbers,target);
		
		System.out.println(answer);
		
	}
	
    public static int solution(int[] numbers, int target) {
    	
    	targetNum = target;
    	
    	int[] flag = new int[numbers.length];
    	return powerSet( numbers, flag, 0 );
        
    }//solution
    
    private static int powerSet(int[] numbers, int[] flag, int index ) {
    	
    	int cnt = 0 ;
    	
    	// 모든 원소를 가지고 +,- 할 수 있는 경우의 수를 구하면서 3인경우만 + 해준다.
    	
    	if ( index == flag.length ) {
    			int result = 0 ;
    		for ( int i = 0 ; i < flag.length; i ++ ) {
    			if ( flag[i] == 1 ) result -= numbers[i];
    			else result += numbers[i];
    		}
    		
    		if ( result == targetNum ) return 1;
    		else return 0;
    	}
    	
    	// 1이면 - 해준다.
    	flag[index] = 1 ;
    	cnt += powerSet(numbers, flag, index+1 );
    	
    	// 0이면 + 해준다
    	flag[index] = 0 ;
    	cnt += powerSet(numbers, flag, index+1);
    	
    	
    	return cnt;
    }

}

나의 풀이

: 처음에 문제를 봤을때.. 도저희 풀이방법이 떠올르지 않아서 검색해본 결과 부분집합 알고리즘의 선행이 필요하였다.

 

부분집합 알고리즘을 이해하고 문제를 다시보니, 부분집합을 조금만 응용하면 되는 문제였다..

 

아는만큼 보이는 것 같다.. ㅠㅠ

 

부분집합 알고리즘 정리 링크 : https://taesan94.tistory.com/60

제출 결과