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

sua·2023년 5월 27일
0

알고리즘 가보자고

목록 보기
33/101

백준 1759번 암호 만들기

문제


나의 풀이

import java.util.*;

public class Main {
    public static boolean check(String password) {
        int ja = 0;
        int mo = 0;
        for(char x : password.toCharArray()) {
            if(x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
                mo += 1;
            } else {
                ja += 1;
            }
        }
        return ja >= 2 && mo >= 1;
    }
    
    public static void go(int n, String alpha[], String password, int i) {
        if(password.length() == n) {
            if(check(password)) {
                System.out.println(password);
            }
            return;
        }
        if(i >= alpha.length) {
            return;
        }
        go(n, alpha, password + alpha[i], i + 1);
        go(n, alpha, password, i + 1);
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String alpha[] = new String[m];
        for(int i = 0; i < m; i++) {
            alpha[i] = sc.next();
        }
        
        Arrays.sort(alpha); // 증가하는 순서를 위함
        go(n, alpha, "", 0);
    }
}

증가하는 순서를 위해 입력 받은 알파벳 배열을 정렬해줘야 한다.
만들어야 하는 암호의 길이 n, 사용할 수 있는 알파벳을 배열로 가지는 alpha, 현재까지 만든 암호 password, 사용할지 말지 결정해야 하는 알파벳의 인덱스 i를 매개변수로 가지는 go 함수를 구현한다.
1) 정답을 찾은 경우
password의 길이 == n
2) 불가능한 경우
i >= alpha의 크기
3) 다음 경우
- i번째를 사용 : go(n, alpha, password + alpha[i], i + 1)
- i번째를 사용 x : go(n, alpha, password, i + 1)

check 함수에서는 최소 한개의 모음과 두개의 자음으로 이루어져있는지 판별해주게 구현한다.

결과


백준 14501번 퇴사

문제


나의 풀이

import java.util.*;

public class Main {
    static int t[];
    static int p[];
    static int n;
    static int answer = 0;
    static void go(int day, int sum) {
        if(day == n + 1) {
            answer = Math.max(answer, sum);
            return;
        }
        if(day > n + 1) {
            return;
        }
        go(day + 1, sum);
        go(day + t[day], sum + p[day]);
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        t = new int[n + 1];
        p = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            t[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }
        go(1, 0);
        System.out.println(answer);
    }
}

day 일이 되었고, 이 날짜에 상담을 할지 말지 결정해야 하는 day와 지금까지 얻은 수익 sum을 매개변수로 가지는 go 함수를 구현해야 한다.

1) 정답을 찾은 경우
day == n + 1
2) 불가능한 경우
day > n + 1
3) 다음 경우 호출
- 상담을 하는 경우 : go(day + T[day], sum + P[day])
- 상담을 하지 않는 경우 : go(day + 1, sum)

결과


백준 14889번 스타트와 링크

문제


나의 풀이

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() != n / 2) {
                return -1;
            }
            if(second.size() != n / 2) {
                return -1;
            } 
            int t1 = 0;
            int t2 = 0;
            for(int i = 0; i < n / 2; i++) {
                for(int j = 0; j < n / 2; j++) {
                    if(i == j) {
                        continue;
                    }
                    t1 += s[first.get(i)][first.get(j)];
                    t2 += s[second.get(i)][second.get(j)];
                }
            }
            return Math.abs(t1 - t2);
        }
        
        if(first.size() > n / 2 || second.size() > n / 2) {
            return -1;
        }
        
        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) 불가능한 경우
- first의 크기 > n / 2
- second의 크기 > n / 2
3) 다음 경우
- 1번 팀 : go(index, first, second)
- 2번 팀 : go(index, first, second)
- 두 경우 모두 호출 전에 first 또는 second에 index를 넣고, 호출 후에 빼는 과정이 필요

결과

profile
가보자고

0개의 댓글