알고리즘 문제풀이 3-5

문제 1 / 여행가의 등산

목표 : (1, 1) -> (N, N) 까지 이동하는 최소 체력소모 구하기

해결방법 : BFS로 풀었다.

시작점은 0이고 나머지 부분들엔 0이상 100이하의 이동 체력 소모 값이 있다.
우선순위로 체력 소모가 덜 되는 순서로 만들어서 (N, N)까지 가면서 dist 배열에 이동 체력 소모를 최솟값으로 갱신해줬다.

import java.util.*;

class Solution {
    static int answer, N;
    static int[][] arr, dist;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, -1, 0, 1};
    static class Point {
        int y, x, stamina;
        public Point(int y, int x, int stamina) {
            this.y = y;
            this.x = x;
            this.stamina = stamina;
        }
    }
    public int solution(int N, int[][] arr) {
        this.N = N;
        this.arr = arr;
        dist = new int[N][N];
        for(int[] dis : dist) {
            Arrays.fill(dis, Integer.MAX_VALUE);
        }
        dist[0][0] = 0;

        PriorityQueue<Point> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.stamina - o2.stamina;
        });
        pq.offer(new Point(0, 0, 0));

        while(!pq.isEmpty()) {
            Point cur = pq.poll();
            int cy = cur.y;
            int cx = cur.x;
            int stamina = cur.stamina;

            if(stamina > dist[cy][cx]) continue;
            
            for(int i=0; i<4; i++) {
                int ny = cy + dy[i];
                int nx = cx + dx[i];
                if(ny<0 || nx<0 || ny>=N || nx>=N) continue;

                int newStamina = stamina + Math.abs(arr[ny][nx] - arr[cy][cx]);
                if(newStamina < dist[ny][nx]) {
                    dist[ny][nx] = newStamina;
                    pq.offer(new Point(ny, nx, newStamina));
                }
            }
        }
        return dist[N-1][N-1];
    }
}

문제 2 / 프로틴 음료

목표 : K개 이하의 프로틴을 골라 M 이상의 단백질을 얻을 수 있는 조합의 수 구하기
단, 음료의 갯수는 홀수여야 한다.

해결방법 : DFS로 풀었다.

현재 음료를 구매하는 경우와 현재 음료를 구매하지 않는 경우로 나누어 재귀적으로 구해주었다.
단, 음료 갯수가 홀수인 경우만 카운팅해달라는 제한사항이 있어서 단백질이 M이 넘지만 음료 갯수가 짝수인 경우는 제외했다.

class Solution {
    static int N, K, M, answer;
    static int[] arr;
    public int solution(int N, int K, int M, int[] arr) {
        answer = 0;
        this.N = N;
        this.K = K;
        this.M = M;
        this.arr = arr;

        dfs(0, 0, 0);

        return answer;
    }
    static void dfs(int idx, int cnt, int sum) {
        if(cnt > K) return;

        if(idx == N) {
            if(cnt%2==1 && sum >= M) {
                answer++;
            }
            return;
        }
        // 현재 음료 구매
        dfs(idx + 1, cnt + 1, sum + arr[idx]);
        // 현재 음료 미구매
        dfs(idx + 1, cnt, sum);
    }
}

문제 3 / 로또 30

목표 : 로또 당첨 횟수 구하기

해결방법 : 정렬로 풀었다.

로또 번호는 6개의 숫자가 동일하면 되기 때문에 순서 어떻든 순서만 맞춰줘서 6개의 숫자가 모두 동일한지 체크해주면 된다.

그래서 나의 선택 번호와 로또 번호들을 모두 정렬해 6개의 숫자가 모두 동일하면 카운팅을 해줬다.

import java.util.*;

class Solution {
    public int solution(int N, int[] selected, int[][] lottos) {
        int answer = 0;

        Arrays.sort(selected);
        for(int[] lotto : lottos) {
            Arrays.sort(lotto);
        }

        for(int i=0; i<lottos.length; i++) {
            int cnt = 0;
            for(int j=0; j<lottos[i].length; j++) {
                if(selected[j] != lottos[i][j]) break;
                cnt++;
            }
            if(cnt==selected.length) answer++;
        }
        return answer;
    }
}