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

타겟 넘버

풀이

• 음이 아닌 정수들이 배열로 주어지고, 이 정수들을 적절히 더하거나 빼서 타겟 넘버를 만들어야 함
• 2차원 배열 만들어서, 0번째 행에는 음이 아닌 정수를 넣고, 아래 행에는 음으로 만든 정수를 넣는다.
• 순서를 바꾸지 않고 타겟 넘버를 만들라고 했으므로, 일단 (0,0) 에서 시작 또는 (1,0) 에서 시작해야 된다. 그리고 오른쪽 혹은 오른쪽 대각선 아래, 오른쪽 대각선 위로만 이동할 수 있다. 따라서 int[] dx = {0,-1,1}, int[] dy={1,1,1} 로 이동하게 함.
• dfs(0,0) , dfs(0,1) 로 각각 dfs 돌려서 target이랑 합이 같아지면 answer++ 해줌.
• 프로그래머스에 적응이 안돼서(?) 다 글로벌로 빼서 썼는데 매우 지저분하다...ㅎ히히;;
  - ....다른사람 풀이 보니까 나 좀 신기하게 푼거같다........ 굳이 왜이렇게 풀었을까 싶음^^^...

코드

import java.util.*;
import java.io.*;
class Solution {

    static int[] dx = {0,-1,1};
    static int[] dy = {1,1,1};
    static int answer = 0;
    static int size;
    static int targetNum;
    static int[][] map;
    static boolean[][] visited;
    public int solution(int[] numbers, int target) {
        size = numbers.length;
        targetNum = target;
        map = new int[2][size];
        
        
        for(int i=0;i<size;i++){
            int num = numbers[i];
            map[0][i] = num;
            map[1][i] = -num;
        }
        visited = new boolean[2][size];
        dfs(0,0,map[0][0]);
        visited = new boolean[2][size];
        dfs(1,0,map[1][0]);
        
        
        return answer;
    }
    
    public static void dfs(int i, int j, int sum){
        visited[i][j] = true;
        if((i==0 && j==size-1 && sum==targetNum)|| (i==1 && j==size-1 && sum==targetNum)){
            answer++;
        }
        
        for(int m=0;m<3;m++){
            int nx = i+dx[m];
            int ny = j+dy[m];
            
            if(nx>=0 && nx<2 && ny>=0 && ny<size && !visited[nx][ny]){
                dfs(nx,ny,sum+map[nx][ny]);
                visited[nx][ny] = false;
            }
        }
    }
    
}