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


이 문제는 재귀로 쉽게 해결할 수 있습니다.


문제 해결 순서는


1. 해당 범위의 값이 같은지 확인한다.

2. 1에서 같으면 그 값을 출력한다.

3. 1에서 다르면 '('를 출력하고 재귀를 통해 해당 영역을 4개로 나눈다.

4. 재귀로 들어가서 1 ~ 3까지 순서를 반복한다.

5. 재귀호출이 끝나고 ')'를 출력한다.


풀 코드입니다.

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
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[1 << 6][1 << 6 + 1];
 
bool isSame(int x1, int y1, int x2, int y2) {
    char tmp = map[x1][y1];
 
    for (int i = x1; i <= x2; i++) {
        for (int j = y1; j <= y2; j++) {
            if (tmp != map[i][j]) return 0;
        }
    }
 
    return 1;
}
 
void f(int x1, int y1, int x2, int y2) {
 
    if (isSame(x1, y1, x2, y2)) cout << map[x1][y1];
    else {
        cout << '(';
        int midX = (x1 + x2) / 2;
        int midY = (y1 + y2) / 2;
 
        f(x1, y1, midX, midY);
        f(x1, midY + 1, midX, y2);
        f(midX + 1, y1, x2, midY);
        f(midX + 1, midY + 1, x2, y2);
        cout << ')';
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) cin >> map[i];
    
    f(0, 0, n - 1, n - 1);
    
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[12841] 정보대 등산  (0) 2017.08.23
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27
[14649] 문홍안  (0) 2017.07.27

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


처음에

모든 친구들에 대해서 만족하는 점을 찾으면 되겠다고 생각했습니다.

그래서 이분탐색으로 접근을 했습니다.

하지만 1차원 선상에서 소수(double)에서도 모일 수 있으므로

이분탐색을 사용하기가 애매했습니다.


그래서 다시 생각했는데 

구현하는 것이 정말 단순했습니다.


그냥 N의 시간으로 가면서 모든 학생들이 모일 수 있는 포인트로 좁혀가다가

그 포인트에 벗어나는 학생이 있으면 홍수에 당하는 것이고 아니라면 만날 수 있는 것이라고 생각했습니다.


minPos와 maxPos가 모든 학생들이 접근할 수 있는 범위입니다.


for문안에서 left와 right는 시간 * 속력으로 이동할 수 있는 거리를 구하여 현재 위치에서 더하고 빼서 

움직일 수 있는 범위를 나타냅니다.


첫번째 if문이 있는 경우가 아니라면 모일 수 있는 것입니다.


풀코드입니다.

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
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
 
#define ll long long
#define MOD ((int)1e9 + 9)
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
 
pii v[(int)5e5];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    double t;
 
    cin >> n >> t;
 
    for (int i = 0; i < n; i++) {
        cin >> v[i].first ;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> v[i].second;
    }
 
    double minPos = 0, maxPos = INF;
 
    for (int i = 0; i < n; i++) {
        double left = v[i].first - v[i].second * t;
        double right = v[i].first + v[i].second * t;
 
        if (maxPos < left || right < minPos) {
            puts("0");
            return 0;
        }
        
        maxPos = min(maxPos, right);
        minPos = max(minPos, left);
    }
 
    puts("1");
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30
[1913] 달팽이  (0) 2017.07.27
[14649] 문홍안  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24

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


이 문제는 사실 N이 크지 않아서

숫자 1이 있는 곳 부터 차례대로 배열에 숫자를 채워나가도 됩니다.


하지만 저는 y=x와 y=-x의 직선으로 4칸으로 나눠서 문제를 해결했습니다.


toNum()함수를 사용하면 1의 시간으로 해당 위치의 숫자를 찾아낼 수 있습니다.


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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
int abs(int n) {
    return n >= 0 ? n : -n;
}
 
int toNum(int i, int j) {
    if (abs(i) <= j) return 4 * j * j - j + i + 1;
    else if (abs(i) <= -j) return 4 * j * j - 3 * j - i + 1;
    else if (abs(j) <= -i) return 4 * i * i + 3 * i + j + 1;
    else return 4 * i * i + i - j + 1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    n /= 2;
 
    int k;
    cin >> k;
 
    pii pos;
 
    for (int i = -n; i <= n; i++) {
        for (int j = -n; j <= n; j++) {
            //toNum함수를 이용하여 1의 시간으로 해당 좌표의 숫자를 알아낼 수 있음.
            int ret = toNum(i, j);
            cout << ret << ' ';
 
            //입력받은 k와 같으면 pos변수에 저장
            if (ret == k) {
                pos.first = i, pos.second = j;
            }
        }
        cout << '\n';
    }
 
    cout << pos.first + n + 1 << ' ' << pos.second + n + 1;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29
[14649] 문홍안  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13

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


단순 구현 문제입니다.


N이 100이기 때문에 시간복잡도 N^2으로 해결할 수 있습니다.


그냥 한번씩 다 밟아보면서 카운트하고

mod를 이용하여 어떤 색인지 판별하면 되겠습니다.


코드입니다.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int pos[100];
char direct[100];
 
int cnt[101];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int p;
    cin >> p;
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> direct[i];
    }
 
    //N^2의 복잡도로 돌 
    for (int i = 0; i < n; i++) {
        int d = (direct[i] == 'L' ? -1 : 1);
 
        for (int j = pos[i] + d; j > 0 && j <= 100; j += d) {
            cnt[j]++;
        }
    }
 
    int b, r, g;
    b = r = g = 0;
    
    //나머지 연산을 이용하여 개수 체킹
    for (int i = 1; i <= 100; i++) {
        int mod = cnt[i] % 3;
        if (mod == 0) b++;
        else if (mod == 1) r++;
        else g++;
    }
 
    //2자리로 고정하기
    cout << fixed;
    cout.precision(2);
    cout << ((double)b / 100) * p << '\n';
    cout << ((double)r / 100) * p << '\n';
    cout << ((double)g / 100) * p << '\n';
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[14488] 준오는 급식충이야!  (0) 2017.07.29
[1913] 달팽이  (0) 2017.07.27
[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13
[5527] 전구 장식  (0) 2017.07.05

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


2차원 DP로 정의하시면 쉽게 해결할 수 있습니다.


dp[자리수][현재 수]라고 정의하면 되겠습니당.


그리고 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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
ll dp[65][10];
int n;
 
ll f(int d, int now) {
    if (d == n) return 1;
 
    ll &ret = dp[d][now];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = now; i < 10; i++) {
        ret += f(d + 1, i);
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(dp, -1, sizeof(dp));
 
        cin >> n;
 
        ll ret = 0;
        for (int i = 0; i < 10; i++) ret += f(1, i);
 
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1890] 점프  (0) 2017.09.15
[2565] 전깃줄  (0) 2017.09.07
[12026] BOJ 거리  (0) 2017.07.24
[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24

https://www.acmicpc.net/source/6343472


사이클이 몇개인지 찾는 문제입니다.!


인풋에서 1차원 배열에 다음 노드가 뭔지 저장 하고!

방문체크 하면서 들어갔던 곳으로 또가면 싸이클이 형성이되겠죠!


여기서 싸이클 종류가 두개가 생기죠!!

1. 순열 싸이클

2. 구냥 싸이클


1번은 문제에서 제시한거처럼 시작점으로 다시 돌아오는 사이클을 '순열 사이클'이라고 하는거같아요!

2번은 시작점을 제외한 노드로 다시 방문하는 경우 순열 사이클이 아니겠지요~~~


코드 보시면 이해가실거에욥!!


코드입니당.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int nextNode[1001];
bool visit[1001];
 
bool isCycle(int start, int now) {
    visit[now] = 1;
 
    if (nextNode[now] == start) return 1; //다음 노드가 시작점이면 싸이클이 맞으므로 리턴
    else if (visit[nextNode[now]]) return 0; // 시작점이 아닌데 방문했던 곳을 방문한다?? 온전한 순열 사이클이 아니죵
    else return isCycle(start, nextNode[now]); // 방문안했으면 무작정 들어가기!!!!!!!!!!!
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
        int n;
        cin >> n;
 
        for (int i = 1; i <= n; i++) {
            cin >> nextNode[i];
        }
 
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            if (visit[i]) continue;
            ret += isCycle(i, i);
        }
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[2667] 단지번호붙이기  (0) 2017.09.15
[10216] Count Circle Groups  (0) 2017.08.10
[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01

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


음..

next_permutation??이라는 함수가 있습니다.

알고리즘 헤더에 있는 함수인데..

이거 쓰면 엄청 쉽게 풀 수 있는데!!!!!!!!!!


기초가 튼튼해야합니다!


dfs로 해봅시다!!!!!!!!!!!!!!!!!!!!!!

그냥 배열을 n의 최대값만큼 만들어서

방문체크하면서 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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
bool visit[10];
int output[10];
 
void f(int num, int d, int n) {
    output[d] = num;
 
    if (d == n) {
        for (int i = 1; i <= n; i++) cout << output[i] << ' ';
        cout << '\n';
        return;
    }
 
 
    for (int i = 1; i <= n; i++) {
        if (visit[i]) continue;
        visit[i] = 1;
        f(i, d + 1, n);
        visit[i] = 0;
    }
}
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        visit[i] = 1;
        f(i, 1, n);
        visit[i] = 0;
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 탐색' 카테고리의 다른 글

[10216] Count Circle Groups  (0) 2017.08.10
[10451] 순열 사이클  (0) 2017.07.27
[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23

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


전형적인 DP문제네요.

1차원 DP이구요

정의는 n까지가는데 최소 비용이라고 정의하면 되겠습니다.


메모이제이션을 하면서 재귀를 돌렸습니다.


문제 풀 떄 꿀팁은 인풋을 받을 때가 중요합니다.

B = 0

O = 1

J = 2

로 배열에 저장했습니다.


그래서 B다음에 O로 갈 땐 (arr[현재 위치] + 1) % 3 == arr[다음 위치] 이 조건이 성립하는 곳으로 이동하시면 됩니다.


코드입니다.

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
#include <iostream>
#include <vector>
 
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int street[1000];
 
int dp[1000];
int n;
 
int min(int a, int b) {
    return a < b ? a : b;
}
 
int dfs(int pos) {
    if (pos == n - 1) return 0;
 
    int &ret = dp[pos];
    if (ret != -1) return ret;
    ret = INF;
    
    for (int i = pos + 1; i < n; i++) if(street[i] == (street[pos] + 1) % 3) ret = min(ret, dfs(i) + (i - pos) * (i - pos));
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'B') street[i] = 0;
        else if (c == 'O') street[i] = 1;
        else street[i] = 2;
    }
 
    memset(dp, -1, sizeof(dp));
 
    int ret = dfs(0);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2565] 전깃줄  (0) 2017.09.07
[2688] 줄어들지 않아  (0) 2017.07.27
[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09

+ Recent posts

티스토리툴바