1,2,3 더하기
정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제
전체 경우의 수는 3^n보다 작거나 같다.
3^10 = 59049, 모든 경우의 수를 체크해주면 됨.
-
기준을 정해서 코드를 짜야함.
-
1,2,3 더하기의 기준은 : 위치.
-
재귀함수로 풀 때 기준을 가지는 것이 중요함. 그리고 그 기준이 함수로 구현.
-
위치 = 사용한 수의 개수랑 같음.
-
cnt : 사용한 수의 개수
-
sum : 합
-
재귀함수 go(cnt, sum, n)
-> return 값이 경우의 수.
1) 다음 경우 호출
1. 1을 사용함 : go(cnt+1,sum+1,n)
2. 2를 사용함 : go(cnt+1,sum+2,n)
3. 3을 사용함 : go(cnt+1,sum+3,n)
2) 정답을 찾은 경우
sum == n과 같은 경우
3) 불가능한 경우
1. 문제의 조건을 위배
2. sum > n
import java.util.Scanner;
public class Main {
static int go(int cnt,int sum,int n) {
int res = 0;
if(sum>n) return 0;
if(sum==n) return 1;
for(int i=1;i<=3;i++) {
res += go(cnt+1, sum+i, n);
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for(int i=0;i<num;i++) {
int n = sc.nextInt();
System.out.println(go(0,0,n));
}
}
}
재귀함수를 사용하지 않고도 풀 수 있음.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int arr[] = new int[11];
arr[1]=1;
arr[2]=2;
arr[3]=4;
//1,2,3을 넣었을 때의 경우의 수를 지정.
for(int i=0;i<num;i++) {
int a = sc.nextInt();
for(int j=4;j<=a;j++) {
arr[j]= arr[j-1] + arr[j-2] + arr[j-3];
}
System.out.println(arr[a]);
}
}
}암호 만들기
서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성
암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어있어야 함.
암호로 사용할 수 있는 문자의 종류는 C가지
가능성 있는 암호를 모두 구하는 문제
1) 암호의 길이는 L
2) 암호는 소문자
3) 암호 최소 한개의 모음
4) 암호 최소 두개의 자음
5) 알파벳 증가 -> 구현으로 증가 감지가 가능함. 알파벳을 오름차순으로 정렬.
6) 암호로 사용할 수 있는 문자의 종류는 C가지
- 각각의 알파벳을 암호에 사용하는지 안하는지를 결정해서 t/f로 표시해줌.
- 시간복잡도는 O(2^c), (3<=L<=C<=15)
- 2^15 = 32768 모든 가능성 있는 경우의 수를 다 구해도 괜찮음.
1) 알파벳을 정렬
2) index : 몇번째 알파벳
3) password : 만든 암호
go( n, alpha, password, i)
- n : 만들어야 하는 암호의 길이
- alpha : 사용할 수 있는 알파벳 ( 총 c가지 )
- password : 현재까지 만든 암호
- i : index 사용할지 말지 결정하는 알파벳 인덱스
- 다음 경우 호출
1. 알파벳을 사용한다. alpha[i]
i->i+1-
password -> 현재까지 만든 암호에 password + alpha[i]
=> go(n, alpha,password+alpha[i],i+1)
-
- 알파벳을 사용하지 않는 경우
1. i->i+1-
password는 그대로
=> go(n,alpha,password,i+1)
-
=> 암호를 만들 때 모든 알파벳을 다 써보기 위해서는 두 가지 경우를 메소드에 적어주면 된다. 두 가지 경우를 재귀로 호출하게 되면 알파벳 c개를 통해서 해볼 수 있는 모든 조합의 암호를 다 만들어 볼 수 있다. 그니까 결국 두개 다 호출하는 이유는 모든 경우의 수를 다 조합해보기 위함이라고 생각하면 된다.
- 정답을 찾은 경우
password의 길이가 n과 같은 경우.
한개의 모음과 두개의 자음이 들어있는지를 확인해주어야함.
이것을 check함수를 통해서 처리해줌.
- 불가능한 경우
i >= alpha의 크기
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static boolean chk(String password) {
int ja = 0;
int mo = 0;
for(int i=0;i<password.length();i++) {
if(password.charAt(i)=='a' || password.charAt(i)=='e' ||
password.charAt(i)=='i' || password.charAt(i)=='o' ||
password.charAt(i)=='u') {
mo += 1;
}else {
ja +=1;
}
}
return ja>=2 && mo >=1;
}
static void go(int n, String alpha[], String password, int i) {
if(password.length()==n) {
if(chk(password)) {
System.out.println(password);
}
return;
}
if(alpha.length<=i)
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 l=sc.nextInt();
int c=sc.nextInt();
String alpha[]= new String[c];
for(int i=0;i<c;i++) {
alpha[i]=sc.next();
}
Arrays.sort(alpha);
go(l,alpha,"",0);
}
}비교적 쉬운 문제였다.....어제 문제가 너무 헬이여서 오늘은 다 쉬워보이네..
퇴사
N+1일이 되는 날 퇴사를 하려고 한다.(1<=N<=15)
남은 N일 동안 최대한 많은 상담을 하려고 한다
하루에 하나의 상담을 할 수 있고
i일에 상담을 하면 T[i]일이 걸리고 P[i]원을 번다.
버는 돈의 최댓값을 구하는 것이 목표임.
- 최대 n일이고 기준은 각각의 날짜가 기준이 됨.
- 상담을 한다 / 안한다에 따라 변하는 것
1. 날짜- 수입 -> p[i]만큼의 돈을 벌 수 있음.
=> go(day,sum)
day일이 되었다. day일에 있는 상담을 할지 말지 결정.
지금까지 얻은 총 수익을 sum으로 계산함.
sum : day-1일까지의 수익을 뜻함.
- 상담을 한다
go(day+T[day],sum+P[day]) - 상담을 안한다
go(day+1,sum)
- 정답을 찾은 경우
day == n+1
- 불가능한 경우
day > n+1
-시간복잡도는 O(2^n)
import java.util.*;
public class Main {
static int n;
static int t[];
static int p[];
static int max =0;
static void go(int day, int sum) {
if(day==n) {
if(max<sum) max=sum;
return;
}
if(day>n) {
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];
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(max);
}
}
코드의 설명을 위에 써두어서 따로 설명할게 없다,,
최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.
