[코딩테스트] 브루트 포스(재귀)

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

1,2,3 더하기 (9095번)

https://www.acmicpc.net/problem/9095

문제
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복선택 가능)

입력
테스트 케이스의 개수 T, (0 ≤ N ≤ 10)

출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

• 최대 방법의 개수 3^10=59049
• 재귀 : 기준을 정한다(위치=사용한 갯수=count), 기준이 바뀔때 변하는 값을 함수 인자로(합이 변함=sum)

1. 다음 경우 호출(하나의 함수가 다른 함수 호출할 때 어떻게 호출할 수 있는지, 각각 값이 어떻게 변하는지. 1을 사용/2를 사용/3을 사용)
2. 정답을 찾은 경우(sum==n)
3. 불가능한 경우(문제의 조건을 위배, 절대로 답을 구할 수 없음. sum>n)

import java.util.*;

public class Main {
	static int num;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i=0; i<t; i++) {
			int n = sc.nextInt();
			go(n,0,0);
			System.out.println(num);
			num=0;
		}

	}

	private static void go(int n, int count, int sum) {
		if(sum>n)
			return;
		if(sum==n)
			num++;
		for(int i=1; i<=3; i++) {
			go(n,count+1,sum+i);
		}
	}
}

-> count는 지워도 됨. 브루트포스3 할 때 다른 풀이 찾으면서 재귀 코드 보고 어렵다했던 문제인데 직접 재귀로 풀었다! 신남!

1,2,3 더하기 (1759번)

https://www.acmicpc.net/problem/1759

문제

• 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성
• 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열
• 암호로 사용할 수 있는 문자의 종류 C가지
• 가능성 있는 암호를 모두 구하는 문제

입력
두 정수 L, C (3 ≤ L ≤ C ≤ 15) C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

풀이

• N과 M 2와 유사. 증가하는 순서로 배열, 중복x, 최소 한 개의 모음+두개의 자음
• 시간복잡도 O(2^15) = 32768
• 알파벳을 정렬, 몇 번째 알파벳인지 index, 만든 암호 password

1. 다음 경우 호출(알파벳을 사용한다)

• alpha[i], i->i+1, password -> password+alpha[i]
• go(n, alpha, password+alpha[i], i+1)
• 알파벳을 사용하지 않는 경우(i -> i+1) go(n, alpha, password, i+1)

1. 정답을 찾은 경우 password 길이 == n, 최소 한개 모음 + 두개 자음
2. 불가능한 경우 index >= alpha 크기

import java.util.*;

public class Main {
	static String password;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int l = sc.nextInt();
		int c = sc.nextInt();
		char al[] = new char[c];
		for(int i=0; i<c; i++) {
			al[i] = sc.next().charAt(0);
		}
		Arrays.sort(al);
		go(l,al,"",0);
	}

	private static void go(int l, char[] al, String password, int i) {
		if(password.length()==l) {
			if(check(password))
				System.out.println(password);
			return;
		}
		if(i>=al.length)
			return;
		go(l, al, password+al[i], i+1);
		go(l, al, password, i+1);
	}

	private 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++;
			else
				ja++;
		}
		if(ja>=2 && mo >= 1)
			return true;
		else
			return false;
	}
}

• 시간복잡도 O(2^C x L)

퇴사 (14501번)

https://www.acmicpc.net/problem/14501

문제

• N+1일이 되는 날 퇴사를 하려 한다(1 ≤ N ≤ 15)
• 남은 N일 동안 최대한 많은 상담을 하려고 한다
• 하루에 하나의 상담을 할 수 있고
• i일에 상담을 하면 T[i]일이 걸리고 P[i]원을 번다

입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

풀이

• 날짜 : 기준(상담을 한다, 안 한다) -> 변하는 것 : 날짜, 수입 go(day,sum)
• sum : day-1 일까지 수익

1. 다음 경우

• 상담을 한다 go(day+T[ day ] , sum+p[ day ])
• 상담을 안한다 go(day+1,sum)

1. 정답을 찾은 경우 day==n+1
2. 불가능한 경우 day > n+1

import java.util.*;

public class Main {
	static int n;
	static int[] t;
	static int[] p;
	static int ans = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		t = new int[n];
		p = new int[n];
		for(int i=0; i<n; i++) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
		}
		go(0,0);
		System.out.println(ans);
	}

	private static void go(int day, int sum) {
		if(day==n) {
			if(ans<sum)
				ans=sum;
			return;
		}
		if(day>n)
			return;
		go(day+1,sum);
		go(day+t[day],sum+p[day]);
	}
}

• 시간 복잡도 O(2ⁿ)