알고리즘 문제풀이 3-5

문제 1 / 여행가의등산

-목표 : N X N 크기의 보드에서 (1,1)에서 (N,N)까지 이동하여 최소한의 체력 소모로 도착하는 최단 경로를 찾는 프로그램을 구현  

 

문제 풀이

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int N, int[][] arr) {
        int[][] energy = new int[N][N];
        for (int[] row : energy) Arrays.fill(row, Integer.MAX_VALUE);

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        pq.offer(new int[]{0, 0, 0}); // {x, y, cost}
        energy[0][0] = 0;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int x = current[0], y = current[1], cost = current[2];

            if (x == N - 1 && y == N - 1) return cost;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    int nextCost = cost + Math.abs(arr[nx][ny] - arr[x][y]);
                    if (nextCost < energy[nx][ny]) {
                        energy[nx][ny] = nextCost;
                        pq.offer(new int[]{nx, ny, nextCost});
                    }
                }
            }
        }

        return -1;
    }
}

---

문제 2 / 프로틴 음료

-목표 : K개 이하의 음료를 선택하여 M 이상의 단백질을 섭취헐 수 있는 경우의 수를 계산하는 프로그램을 구현

 

문제 풀이

 

최종 코드

import java.util.*;

class Solution {
    private int count = 0;

    private void findCombinations(int[] arr, int index, int selectCount, int maxSelect, int sum, int minProtein) {
        if (sum >= minProtein && selectCount > 0 && selectCount <= maxSelect) {
            count++;
        }
        if (index >= arr.length || selectCount >= maxSelect) {
            return;
        }

        findCombinations(arr, index + 1, selectCount + 1, maxSelect, sum + arr[index], minProtein);

        findCombinations(arr, index + 1, selectCount, maxSelect, sum, minProtein);
    }

    public int solution(int N, int K, int M, int[] arr) {
        count = 0;
        findCombinations(arr, 0, 0, K, 0, M);
        return count;
    }
}

---

문제 3 / 로또 30

-목표 : 여러 개의 로또를 구매하고 당첨 번호와 비교하여 각 등수별 당첨 횟수를 계산하는 프로그램을 구현

 

문제 풀이

 

최종 코드

import java.util.*;
class Solution {
    public int solution(int N, int[] selected, int[][] lottos) {
        int answer = 0;

        for(int[] winnum : lottos){
            Set<Integer> winset = new HashSet<>();
            for(int num : winnum){
                winset.add(num);
            }
            int matchCount = 0;
            for(int num : selected){
                if(winset.contains(num)){
                    matchCount++;
                }
            }
            if(matchCount == 6){
                answer++;
            }

        }

        return answer;
    }
}

---