백준 15661번 링크와 스타트

문제

나의 풀이

import java.util.*;

public class Main {
    static int s[][];
    static int n;
    static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
        if(index == n) {
            if(first.size() == 0) {
                return -1;
            }
            if(second.size() == 0) {
                return -1;
            }
            int t1 = 0;
            int t2 = 0;
            for(int i = 0; i < first.size(); i++) {
                for(int j = 0; j < first.size(); j++) {
                    if(i == j) {
                        continue;
                    }
                    t1 += s[first.get(i)][first.get(j)];
                }
            }
            for(int i = 0; i < second.size(); i++) {
                for(int j = 0; j < second.size(); j++) {
                    if(i == j) {
                        continue;
                    }
                    t2 += s[second.get(i)][second.get(j)];
                }
            }
           
            return Math.abs(t1 - t2);
        }

        int answer = -1;
        first.add(index);
        int t1 = go(index + 1, first, second);
        if(answer == -1 || (t1 != -1 && answer > t1)) {
            answer = t1;
        }
        first.remove(first.size() - 1);

        second.add(index);
        int t2 = go(index + 1, first, second);
        if(answer == -1 || (t2 != -1 && answer > t2)) {
            answer = t2;
        }
        second.remove(second.size() - 1);

        return answer;
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                s[i][j] = sc.nextInt();
            }
        }

        ArrayList<Integer> first = new ArrayList<>();
        ArrayList<Integer> second = new ArrayList<>();
        System.out.println(go(0, first, second));
    }
}

스타트와 링크 문제와 동일하게 index번째 사람을 어떤 팀에 넣을지 결정해야 하고, 1번팀과 2번팀에 속한 사람이 각각 first, second에 들어있는 세개의 매개변수로 이루어진 go 함수를 구현해야 한다.

1) 정답을 찾은 경우
index == n
2) 다음 경우
- 1번 팀 : go(index, first, second)
- 2번 팀 : go(index, first, second)
- 두 경우 모두 호출 전에 first 또는 second에 index를 넣고, 호출 후에 빼는 과정이 필요

다른 부분은 팀을 n/2명으로 나누는 것이 아니기 때문에 for문을 돌릴 때 n/2만큼이 아니라 size만큼 돌려야 하고 예외 처리를 할 때도 n/2가 아닐 때 -1을 리턴하는게 아니라 0일때 -1을 리턴하게 해야 한다.

결과

백준 2529번 부등호

문제

나의 풀이

import java.util.*;

public class Main {
    static int n;
    static char a[] = new char[20];
    static ArrayList<String> answer = new ArrayList<>();
    static boolean check[] = new boolean[10];
    static boolean good(char x, char y, char op) {
        if(op == '<') {
            if(x > y) {
                return false;
            }
        }
        if(op == '>') {
            if(x < y) {
                return false;
            }
        }
        return true;
    }
    
    static void go(int index, String num) {
        if(index == n + 1) {
            answer.add(num);
            return;
        }
        for(int i = 0; i <= 9; i++) {
            if(check[i]) {
                continue;
            }
            if(index == 0 || good(num.charAt(index - 1), (char)(i + '0'), a[index - 1])) {
                check[i] = true;
                go(index + 1, num + Integer.toString(i));
                check[i] = false;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            a[i] = sc.next().toCharArray()[0];
        }
        go(0, "");
        Collections.sort(answer);
        System.out.println(answer.get(answer.size() - 1));
        System.out.println(answer.get(0));
    }
}

go 함수 호출 중간에 절대로 정답이 될 수 없는 경우를 발견하면 그 뒤의 호출을 더 이상 진행하지 않아도 되게 한다. good 함수를 통해 유효성을 검사한다.
index가 n + 1이면 정답인 경우므로 answer에 num 문자열을 추가시켜준다.
정답이 아니면 다음 경우이므로 for문을 0부터 9까지 돌면서 check되지 않고 유효한 경우면 num에 추가시켜서 go 함수를 재귀호출하는 방식으로 수행하면 된다.

결과