[프로그래머스-자바] 동적계획법

N으로 표현

• dfs로 풀이하였다.
• 만들수 있는 사칙연산들을 dfs로 만들어냈다.
• count + i를 통해 N의 사용 개수를 나타낸다. number를 통해 연산을 이어나가고, N과 target을 계속 전달해준다.
• 연산 중에 여러 자리 수의 N을 쓸 수 있으므로 getDigit()을 이용한다.
• number가 target과 같으면 answer를 비교하고 return;한다.
• 마지막으로 solution에서 8보다 값이 큰지 보고 크면 -1을 보내준다.

public class Nexpression {
    int answer;

    public int solution(int N, int number) {
        answer = 9;
        dfs(0, 0, N, number);
        return answer > 8 ? -1 : answer;
    }

    private void dfs(int count, int number, int N, int target) {
        if (count > 8) {
            return;
        }

        if (number == target) {
            answer = Math.min(answer, count);
            return;
        }

        for (int i = 1; i <= 8 - count; i++) {
            dfs(count + i, number + getDigit(i, N), N, target);
            dfs(count + i, number - getDigit(i, N), N, target);
            dfs(count + i, number * getDigit(i, N), N, target);
            dfs(count + i, number / getDigit(i, N), N, target);

        }
    }

    private int getDigit(int digit, int N) {
        int result = 0;
        for (int i = 0; i < digit; i++) {
            result += Math.pow(10, i) * N;
        }
        return result;
    }
}

 

정수삼각형

• 아래에서부터 두 개를 비교하여 큰 값을 위항에 더하는 방식으로 올라가면 최댓값은 triangle[0][0]이 된다.

public class IntegerTriangle {
    public int solution(int[][] triangle) {

        for (int i = triangle.length - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].length; j++) {
                triangle[i][j] = triangle[i + 1][j] > triangle[i + 1][j + 1] ? triangle[i][j] + triangle[i + 1][j] : triangle[i][j] + triangle[i + 1][j + 1];
            }
        }
        return triangle[0][0];
    }
}

 

등굣길

• road[0][0] = 1로 두고 시작한다.
• 장애물이 있는 부분은 -1로 표시해둔다.
• for문을 돌면서 장애물 부분은 0으로 바꾸어주고 continue한다.
• i가 0이 아닐 경우에만 위의 항을 더해주고, j가 0이 아닌 경우에만 왼쪽항을 더해준다. 그런식으로 다 더해나가면 마지막 항에 최단경로 개수가 나온다.

public class SchoolRoad {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;

        int[][] road = new int[n][m];
        road[0][0] = 1;

        for (int[] puddle : puddles) {
            road[puddle[1] - 1][puddle[0] - 1] = -1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (road[i][j] == -1) {
                    road[i][j] = 0;
                    continue;
                }
                if (i != 0) {
                    road[i][j] += road[i - 1][j] % 1000000007;
                }
                if (j != 0) {
                    road[i][j] += road[i][j - 1] % 1000000007;
                }
            }
        }
        answer = road[n - 1][m - 1] % 1000000007;
        return answer;
    }
}

 

도둑질

• 두 개의 일차원 배열을 통해 원형의 dp문제를 해결한다.
• dp[]를 통해 첫번째 돈을 얻는 것으로 가정하고 마지막 집은 들리지 않도록 length를 정한다.
• dp2[]를 통해 첫번째 집은 가지 않고, 마지막 집까지 갈 수 있도록 한다.
• 두 배열 중 가장 큰 값이 훔칠 수 있는 최댓값이다.

public class Stealing {
    public int solution(int[] money) {
        int answer = 0;
        int[] dp = new int[money.length - 1];
        int[] dp2 = new int[money.length];

        dp[0] = money[0];
        dp[1] = money[0];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(money[i] + dp[i - 2], dp[i - 1]);
        }
        dp2[0] = 0;
        dp2[1] = money[1];
        for (int i = 2; i < dp2.length; i++) {
            dp2[i] = Math.max(money[i] + dp2[i - 2], dp2[i - 1]);
        }
        answer = Math.max(dp[dp.length - 1], dp2[dp2.length - 1]);
        return answer;
    }
}