BOJ : https://www.acmicpc.net/problem/1062

github : https://github.com/junho0956/Algorithm/blob/master/1062/1062/%EC%86%8C%EC%8A%A4.cpp

 

 

dfs를 통해서 사용가능한 알파벳의 추가/삭제 연산을 해주면서 완전탐색 하듯이 탐색하였습니다.

 

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
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
 
bool visit[26];
int N, K, ans;
vector<string> v;
 
void solve(int al, int pk) {
 
    if (pk == K) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            bool temp = true;
            for (int j = 4; j < v[i].size() - 4; j++) {
                if (visit[v[i][j]-'a'] == false) {
                    temp = false;
                    break;
                }
            }
            if (temp) cnt++;
        }
        ans = max(ans, cnt);
        return;
    }
 
    for (int i = al; i < 26; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            solve(i, pk + 1);
            visit[i] = 0;
        }
    }
 
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    visit['a' - 'a'] = visit['c' - 'a'] = visit['t' - 'a'] = visit['i' - 'a'] = visit['n' - 'a'] = true;
 
    cin >> N >> K;
    if (K < 5) ans = 0;
    else if (K == 26) ans = N;
    else {
        string str;
        for (int i = 0; i < N; i++) {
            cin >> str;
            v.push_back(str);
        }
 
        solve(0, 5);
    }
 
    cout << ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1010번 다리 놓기  (0) 2020.02.08
BOJ 2163번 초콜릿 자르기  (0) 2020.02.08
BOJ 1072번 게임  (0) 2020.02.05
BOJ 15922번 아우으 우아으이야!!  (0) 2020.02.05
BOJ 2170번 선 긋기  (0) 2020.02.05

BOJ : https://www.acmicpc.net/problem/1072

 

** 현재승률이 99%라면 100%가 될 수 없습니다.

** 무작정 +1 씩해가면서 탐색하게 되면 무조건 TLE에 걸리게 됩니다.

** 이분탐색을 이용해서 해결합니다.

 

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
#include <iostream>
#include <math.h>
using namespace std;
 
 
int main() {
    long long X, Y;;
    cin >> X >> Y;
 
    int z = Y * 100 / X;
 
    if (z >= 99) {
        cout << "-1";
        exit(0);
    }
    int low = 0, high = 1000000000;
 
    int result = -1;
 
    while (low <= high){
        int mid = (low + high) / 2;
        int tempz = (100 * (Y + mid)) / (X + mid);
        if (z >= tempz)
        {
            result = mid + 1;
            low = mid + 1;
        }
        else
            high = mid - 1;
    }
 
    cout << result;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2163번 초콜릿 자르기  (0) 2020.02.08
BOJ 1062번 가르침  (0) 2020.02.05
BOJ 15922번 아우으 우아으이야!!  (0) 2020.02.05
BOJ 2170번 선 긋기  (0) 2020.02.05
BOJ 9202번 Boggle  (0) 2020.02.05

BOJ : https://www.acmicpc.net/problem/15922

2170번 선긋기와 같은 문제입니다.

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pii;
int N;
 
vector<pii> v;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        int s, e;
        cin >> s >> e;
        v.push_back({ s,e });
    }
 
    sort(v.begin(), v.end());
 
    int s = v[0].first, e = v[0].second;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int ns = v[i].first, ne = v[i].second;
        if (e < ns) {
            ans += (e - s);
            s = ns, e = ne;
        }
        else e = max(e, ne);
 
    }
    ans += e - s;
 
    cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1062번 가르침  (0) 2020.02.05
BOJ 1072번 게임  (0) 2020.02.05
BOJ 2170번 선 긋기  (0) 2020.02.05
BOJ 9202번 Boggle  (0) 2020.02.05
BOJ 10999번 구간 합 구하기2  (0) 2020.02.05

BOJ : https://www.acmicpc.net/problem/2170

(다음은 같은 문제입니다. https://www.acmicpc.net/problem/15922)

github : https://github.com/junho0956/Algorithm/blob/master/2170/2170/%EC%86%8C%EC%8A%A4.cpp

 

라인스위핑과 관련된 문제라고 하는데

아직 라인스위핑에 대한 정확한 개념을 몰라서 생각나는대로 풀어봤습니다.

조만간 라인스위핑 알고리즘을 공부해서 정리하겠습니다.

 

선 긋기는 왼쪽부터 최대범위를 계속 갱신시켜주면서 전부 탐색하였습니다.

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pii;
int N;
 
vector<pii> v;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        int s, e;
        cin >> s >> e;
        v.push_back({ s,e });
    }
 
    sort(v.begin(), v.end());
 
    int s = v[0].first, e = v[0].second;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int ns = v[i].first, ne = v[i].second;
        if (e < ns) {
            ans += (e - s);
            s = ns, e = ne;
        }
        else e = max(e, ne);
 
    }
    ans += e - s;
 
    cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1072번 게임  (0) 2020.02.05
BOJ 15922번 아우으 우아으이야!!  (0) 2020.02.05
BOJ 9202번 Boggle  (0) 2020.02.05
BOJ 10999번 구간 합 구하기2  (0) 2020.02.05
BOJ 2042번 구간 합 구하기  (0) 2020.02.05

+ Recent posts

티스토리툴바