문제

입력

출력

예제

idea

꼬리물기 식으로 계속해서 진행하기 때문에 dfs라고 생각을 하였다.
이 문제는 x좌표는 오른쪽으로만 y좌표는 위 중간 아래 방향으로 이동하므로 접한 곳은 세곳이다.
또한 중복을 포함하여야 하기 때문에 visitied는 사용하지 않는다.

Code

//하나의 수에서 계속해서 트리 형식으로 진행하므로 dfs로 진행 
class Solution {
    
    static boolean visited[][];
    static int array[][];
    static int num;
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        num=numbers.length;
    	
        visited=new boolean[2][num];
        array= new int[2][num];
        
        for(int i=0;i<2;i++){
            for(int j=0;j<num;j++){
                if(i==0)
                    array[i][j]=numbers[j];
                else
                    array[i][j]=-numbers[j];
                
               //System.out.println(array[i][j]);
            }
        }
        dfs(0,0,array[0][0],target);
        dfs(1,0,array[1][0],target);
        System.out.println(answer);
        return answer;
    }
    
    static public void dfs(int x, int y,int sum,int target) {
        visited[0][0]= true;
        int dx=0,dy=0;
        int di[]={0,1,-1};
        int dj[]={1,1,1};
     
        if(y == num-1)
       		//System.out.println("sum = " + sum);
        if(y == num-1 && sum ==target)
            answer++;
        
        for(int i=0;i<3;i++){
            
            int summ=sum;
            dx=x+di[i];
            dy=y+dj[i];
            
            if(dy>=num||dx>1||dx<0)
                continue;
        	
            //System.out.println(dx + " "+dy);
            
            summ+=array[dx][dy];
            dfs(dx,dy,summ,target);
          
        }    
        
	}
}

결과