BOJ::1759 암호 만들기

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


백트래킹을 통해 결과에 쓰일 String만 만들어주면 된다.

백트래킹을 처음 접했을 때 연습하기 좋은 문제 인거 같다.


<JAVA>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    static int l,c;
    static String a[];
    static int con,vow,cnt;
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        String s = br.readLine();
        a=s.split(" ");
        Arrays.sort(a);
        
        for(int i = 0 ; i < c-l+1;i++){
            cnt=0;
            con=0;
            vow=0;
            dfs(i,a[i]+"");
        }
        
        System.out.print(sb.toString());
    }
    
    public static void dfs(int v,String str){
        cnt++;
        
        if(isVow(a[v])){
            vow++;
        }else{
            con++;
        }
        if(cnt==l){
            if(con>=2 && vow>=1){
                sb.append(str + "\n");
            }
        }else{
            for(int i = v+1; i<c ; i++){
                dfs(i,str+a[i]+"");
            }
        }
        
        cnt--;
        if(isVow(a[v])){
            vow--;
        }else{
            con--;
        }
        
    }
    //모음 확인
    public static boolean isVow(String s){
        if(s.equals("a") || s.equals("e") || s.equals("i") || s.equals("o") || s.equals("u")){
            return true;
        }
        return false;
    }
}
cs



C++


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int l, c,con,vow,cnt;
string result;
string a[16];
 
bool isVow(string s) {
    if (s == "a" || s == "e" || s == "i" || s == "o" || s == "u") {
        return true;
    }
    return false;
}
 
void dfs(int v, string str) {
    cnt++;
    if (isVow(a[v])) {
        vow++;
    }
    else {
        con++;
    }
 
    if (cnt == l) {
        if (vow >= 1 && con >= 2) {
            result += str + "\n";
        }
    }
    else {
        for (int i = v + 1; i < c; i++) {
            dfs(i, str + a[i] + "");
        }
    }
 
    cnt--;
    if (isVow(a[v])) {
        vow--;
    }
    else {
        con--;
    }
}
 
int main() {
    result = "";
    cin >> l >> c;
    for (int i = 0; i < c; i++) {
        cin >> a[i];
    }
    sort(a,a+c);
 
 
    for (int i = 0; i < c - l + 1; i++) {
        cnt = 0;
        vow = 0;
        con = 0;
        dfs(i, a[i]);
    }
 
    cout << result;
 
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

1890 점프  (0) 2017.12.31
1874 스택 수열  (0) 2017.12.31
1697 숨바꼭질  (0) 2017.12.31
1475 방 번호  (0) 2017.12.31
1463 1로만들기  (0) 2017.12.31

+ Recent posts

티스토리툴바