23년 5월 27일 (1) [알고리즘 - 완탐]

sua·2023년 5월 27일
0

알고리즘 가보자고

목록 보기
32/101

백준 10819번 차이를 최대로

문제

나의 풀이

import java.util.*;

public class Main {
    public static boolean next_permutation(int a[]) {
        int i = a.length - 1;
        while(i > 0 && a[i - 1] >= a[i]) { // 1단계
            i -= 1;
        }

        if(i <= 0) {
            return false;
        }

        int j = a.length - 1;
        while(a[j] <= a[i - 1]) { // 2단계
            j -= 1;
        }

        int temp = a[i - 1]; // 3단계
        a[i - 1] = a[j];
        a[j] = temp;

        j = a.length - 1;
        while(i < j) { // 4단계
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    
    public static int calculate(int a[]) {
        int sum = 0;
        for(int i = 1; i < a.length; i++) {
            sum += Math.abs(a[i] - a[i - 1]);
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        Arrays.sort(a);
        int answer = 0;
        do {
            answer = Math.max(answer, calculate(a));
        } while(next_permutation(a));
        
        System.out.println(answer);
    }
}

배열을 정렬해주고 나서(첫순열인 오름차순을 구하기 위해), 순열을 모두 구하면서 그때마다 나오는 값 중에서 최대값을 구하면 된다.

결과


백준 10971번 외판원 순회 2

문제


나의 풀이

import java.util.*;

public class Main {
    public static boolean next_permutation(int a[]) {
        int i = a.length - 1;
        while(i > 0 && a[i - 1] >= a[i]) { // 1단계
            i -= 1;
        }

        if(i <= 0) {
            return false;
        }

        int j = a.length - 1;
        while(a[j] <= a[i - 1]) { // 2단계
            j -= 1;
        }

        int temp = a[i - 1]; // 3단계
        a[i - 1] = a[j];
        a[j] = temp;

        j = a.length - 1;
        while(i < j) { // 4단계
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[][] = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        int d[] = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = i;
        }
        
        int answer = Integer.MAX_VALUE;
        do {
            if(d[0] != 0) {
                break;
            }
            boolean ok = true;
            int sum = 0;
            for(int i = 0; i < n - 1; i++) {
                if(a[d[i]][d[i + 1]] == 0) {
                    ok = false;
                } else {
                    sum += a[d[i]][d[i + 1]];
                }
            }
            if(ok && a[d[n - 1]][d[0]] != 0) {
                sum += a[d[n - 1]][d[0]];
                answer = Math.min(answer, sum);
            }
        } while(next_permutation(d));

        System.out.println(answer);
    }
}

N이 작기 때문에 순열로 풀 수 있다.

결과


백준 6603번 로또

문제


나의 풀이

import java.util.*;

public class Main {
    public static boolean next_permutation(int a[]) {
        int i = a.length - 1;
        while(i > 0 && a[i - 1] >= a[i]) { // 1단계
            i -= 1;
        }

        if(i <= 0) {
            return false;
        }

        int j = a.length - 1;
        while(a[j] <= a[i - 1]) { // 2단계
            j -= 1;
        }

        int temp = a[i - 1]; // 3단계
        a[i - 1] = a[j];
        a[j] = temp;

        j = a.length - 1;
        while(i < j) { // 4단계
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int n = sc.nextInt();
            if(n == 0) {
                break;
            }
            int a[] = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            
            int d[] = new int[n];
            for(int i = 0; i < n; i++) {
                if(i < n - 6) {
                    d[i] = 0;
                } else {
                    d[i] = 1;
                }
            }
            ArrayList<ArrayList<Integer>> answer = new ArrayList<>();
            do {
                ArrayList<Integer> cur = new ArrayList<>();
                for(int i = 0; i < n; i++) {
                    if(d[i] == 1) {
                        cur.add(a[i]);
                    }
                }
                answer.add(cur);
            } while(next_permutation(d));
            
            Collections.sort(answer, new Comparator<ArrayList<Integer>>() {
                public int compare(ArrayList<Integer> l1, ArrayList<Integer> l2) {
                    int n = l1.size();
                    int m = l2.size();
                    int i = 0;
                    while(i < n && i < m) {
                        int t1 = l1.get(i);
                        int t2 = l2.get(i);
                        if(t1 < t2) {
                            return -1;
                        } else if(t1 > t2) {
                            return 1;
                        }
                        i += 1;
                    }
                    if(i == n && i != m) {
                        return -1;
                    } else if(i != n && i == m) {
                        return 1;
                    }
                    return 0;
                }
            });
            
            for(ArrayList<Integer> v : answer) {
                for(int x : v) {
                    System.out.print(x + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}

0을 k - 6개, 1을 6개 넣은 다음에 next_permutation을 수행하면 모든 조합을 구할 수 있다.

결과

profile
가보자고

0개의 댓글