문제1 ) 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

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

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

풀이

방법의 개수 : ?+?+.... = n
1이 n개가 최댓값
? 에는 1,2,3 중에 하나
n번째 올수있는 수도 3가지
--> 3^n개보다 작거나 같다.
n<=10 -> 3^10=59049이므로 별로 크지 않다.
그래서 경우의수를 다 만들어도 괜찮다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	static StringBuilder builder = new StringBuilder();
	static int count;
    static void go(int sum, int goal) {
        if (sum == goal)
        {
        	count++;
        	return;
        }
        if (sum > goal)
            return;
        for (int i=1; i<=3; i++) {
            go(sum+i,goal);
        }
    }
    public static void main(String args[]) throws NumberFormatException, IOException {
    	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    	int T = Integer.parseInt(reader.readLine());
    	while(T-->0)
    	{
    		count=0;
    		int temp = Integer.parseInt(reader.readLine());
    		go(0,temp);
    		builder.append(count).append("\n");
    	}

    	System.out.println(builder);
    }
}

문제 2 ) 암호 만들기

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

4 6
a t c i s w

예제 출력 1

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

풀이

시간복잡도

사용할수있는 암호는 C가지

-> 2^C
2^15 = 32768

내가한 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
	static StringBuilder builder = new StringBuilder();
	static String[] a;
    static boolean[] c;
    static String[] code;
    static void go(int index, int start, int L,int C) {
        if (index == L)
        {
        	StringBuilder temp_builder = new StringBuilder();
        	int consonant = 0;
        	int vowel = 0;
        	  for (int i=0; i<L; i++) {
        		  if(a[i].equals("a") || a[i].equals("e") || a[i].equals("i") ||
        				  a[i].equals("o")|| a[i].equals("u"))
        			  consonant++;
        		  else
        			  vowel++;
        		  temp_builder.append(a[i]);
              }
        	  if(consonant>0 && vowel>1)
        	  {
        		  builder.append(temp_builder);
                  builder.append("\n");
        	  }
              return;
        }
      //start = index번째에 올수있는 수는 start ~ n = i + 1;
        for (int i=start; i<=(C-1); i++) {//1~N중에
            if (c[i]) continue; //c[i]가 true이면 사용한 수 이기 때문에 건너뛰기
            c[i] = true; //i를 사용한것을 체크
            a[index] = code[i]; //i를 index번째 자리에 위치시킴
            go(index+1,i+1, L, C);// 다음 자리로~
            c[i] = false; //다시 사용해야 하므로 false로 초기화
        }
    }

    public static void main(String args[]) throws NumberFormatException, IOException {
    	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    	int L = Integer.parseInt(tokenizer.nextToken());
    	int C = Integer.parseInt(tokenizer.nextToken());
    	tokenizer = new StringTokenizer(reader.readLine());
    	code = new String[C];
    	a = new String[C];
    	 c = new boolean[C];
    	 for (int i=0; i<C; i++)
    	{
    		 code[i] = tokenizer.nextToken();
    	}
    	Arrays.sort(code);
 		go(0,0,L,C);
    	System.out.println(builder);

    }
}

구현

• go(n, alpha, password,i) = L
• n: 만들어야 하는 암호의 길이
• alpha: 사용할수 있는 알파벳
• password: 현재까지 만든 암호
• i: 사용할지 말지 결정해야 하는 알파벳의 인덱스

• 정답을 찾은 경우 (문제의 조건에 맞는지 확인 과정은 여기서 필요함)
• n == password.length()
• 불가능한 경우
• i >= alpha.size()

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);
    }
}

문제 3 ) 퇴사

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일 2일 3일 4일 5일 6일 7일
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 200
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

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

출력

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

예제 입력 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1

45

풀이

날짜에 선택은 2가지이다.
1.선택을 한다.
2.선택을 안한다가 있다.

N은 최대15이기 때문에 시간복잡도는 O(2^N)
2^15 = 32,768

날짜가 기준이고 날짜를 건너뛰면서 가면 됨

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	static StringBuilder builder = new StringBuilder();
    static int[] T = new int[15];
    static int[] P = new int[15];
    static boolean[] c = new boolean[15];
    static int sum;
    static void go(int index, int temp_sum, int n) {
        if (index == n) {
        	if(temp_sum>sum)
        		sum = temp_sum;
            return;
        }
        if (index > n) return;
        go(index+T[index], temp_sum+P[index],n);
        go(index+1, temp_sum, n);
    }

    public static void main(String args[]) throws NumberFormatException, IOException {
    	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    	int N = Integer.parseInt(reader.readLine());
    	StringTokenizer tokenizer;
    	for(int i=0; i<N;i++)
    	{
    		tokenizer = new StringTokenizer(reader.readLine());
    		T[i] = Integer.parseInt(tokenizer.nextToken());
    		P[i] = Integer.parseInt(tokenizer.nextToken());
    	}
    	sum = -1;
 		go(0,0,N);
    	System.out.println(sum);

    }
}