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 함수에서는 최소 한개의 모음과 두개의 자음으로 이루어져있는지 판별해주게 구현한다.
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)
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를 넣고, 호출 후에 빼는 과정이 필요