[코드트리] 2024/08/11 - 최소 점프 횟수, n개의 점 중 m개 고르기

알고리즘 문제풀이

최소 점프 횟수

내 풀이

• Backtracking을 이용한 간단한 문제다.

import java.util.*;

public class Main {
    static int n;
    static int ans = Integer.MAX_VALUE;
    static int[] arr;

    public static void main(String[] args) {
        init();
        solve(0, 0);
        if(ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }

    private static void solve(int cnt, int local) {
        if(local >= n) return;
        if(local == n - 1) {
            ans = Math.min(ans, cnt);
            return;
        }

        for(int i = 1; i <= arr[local]; i++) {
            solve(cnt + 1, local + i);
        }
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];

        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
    }
}

n개의 점 중 m개 고르기

내 풀이

• 멘탈이 너무 흔들렸다..........
• 순서에 상관없이 중복되는 최종값을 고려하는 코드를 짜는 방법을 잊어서 너무 힘든 문제였다..

import java.util.*;

public class Main {
    static int n, m;
    static int ans = Integer.MAX_VALUE;
    static int[][] nodeArr;
    static int[] mArr;
    static boolean[] visited;

    public static void main(String[] args) {
        init();
        solve(0, 0);
        
        System.out.println(ans);
    }

    private static void solve(int idx, int cnt) {
        if(idx == n || cnt == m) {
            if(cnt != m) return;
            int tempDist = Integer.MIN_VALUE;

            for(int i = 0; i < m; i++) {
                for(int j = i + 1; j < m; j++) {
                    int currentDist = uclidian(mArr[i], mArr[j]);
                    tempDist = Math.max(tempDist, currentDist);
                }
            }
            
            ans = Math.min(ans, tempDist);
            return;
        }

		/* 중복값을 고려하지 않아 시간 초과된 접근 방법
        for(int i = cnt; i < n; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            mArr[cnt] = i;
            solve(cnt + 1);
            visited[i] = false;
        }
        */
        
        // 해당 인덱스 위치의 수를 선택하냐 마냐를 통해 중복 값을 제외한 접근
        mArr[cnt] = idx;
        solve(idx + 1, cnt + 1);
        solve(idx + 1, cnt);
    }

    private static int uclidian(int one, int two) {
        int x1 = nodeArr[one][0];
        int y1 = nodeArr[one][1];        
        int x2 = nodeArr[two][0];
        int y2 = nodeArr[two][1];

        return (int) Math.pow(x1 - x2, 2) + (int) Math.pow(y1 - y2, 2);
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        nodeArr = new int[n][2];
        mArr = new int[m];
        visited = new boolean[n];

        for(int i = 0; i < n; i++) {
            nodeArr[i][0] = sc.nextInt();
            nodeArr[i][1] = sc.nextInt();
        }
    }
}