http://koistudy.net/?mid=prob_page&NO=2270&SEARCH=0

 

KOISTUDY

 

koistudy.net

 

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>
 
int n, M, m[101], c[101];
 
//int minimum_cost = 987654321;
 
constexpr int min(int first, int second)
{
    return (((first < second) ? first : second));
}
 
void input()
{
    std::cin >> n >> M;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> m[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> c[i];
    }
}
 
int f(int i, int r)
{
    if (i == 0)
    {
        if (r <= 0)
        {
            return 0;
        }
        else
        {
            return 987654321;
        }
    }
    else if (r <= 0)
    {
        return f(i - 1, r);
    }
    else
    {
        int a = f(i - 1, r - m[i]) + c[i];
        int b = f(i - 1, r);
        //std::cout << i << ' ' << r << '\t' << a << ' ' << b << '\n';
        return min(a, b);
    }
}
 
int main()
{
    input();
    std::cout << f(n, M);
    return 0;
}
 cs

적당히 꼬아놓은 재귀는 참 짜증나는 것 같다

 

사실 이정도 재귀는 금방금방 이해할수잇어야할텐데

 

아무튼, 흐름은 다음과 같다

 

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
int f(int i, int r)
{
    //앱을 다 순회한 경우
    if (i == 0)
    {
        //메모리를 확보한 경우
        if (r <= 0)
        {
            return 0;
        }
        //메모리를 확보하지 못한 경우
        else
        {
            return 987654321;
        }
    }
    else if (r <= 0)
    {
        //앱을 다 순회하지 않았지만 메모리를 확보한 경우, 0을 리턴하기 위해 i를 계속 돌린다.
        return f(i - 1, r);
    }
    else
    {
        //앱을 비활성화 하는 경우, 계속된 재귀로 메모리를 확보한다면 0을 계속 리턴하게 될 것인데
        //재귀의 종료조건을 달성하는 순간 비활성화된 모든 앱의 비용을 더하면서 재귀가 풀린다.
        //그렇게 된다면 a는 해당 메모리들의 비활성화 비용을 합친 값을 가지게 된다.
        int a = f(i - 1, r - m[i]) + c[i];
        //앱을 비활성화 하지 않는 경우
        //다음 앱을 살펴보는 역할을 하거나, 확보해야할 메모리를 건드리지 않기 때문에 9876...을
        //리턴한다. 결과적으로 min에 의해 a의 값을 갖게 된다.
        int b = f(i - 1, r);
        //std::cout << i << ' ' << r << '\t' << a << ' ' << b << '\n';
        return min(a, b);
    }
}
 cs

 

글로 써놔도 직접 돌려보기 전에는 이해가 힘들다.

 

한줄씩 살펴보는 것이 이해와 정신건강에 좋을 것.

 

순열이나 마찬가지다.

 

1 2 3 4 5를

 

1

2

...

5

12

13

...

45

123

124

...

345

1234

1235

2345

12345

 

모든 경우를 살펴보는 것이다.

 

여기서 만약 메모리를 확보하게 된다면

 

    else if (r <= 0)

    {

        //앱을 다 순회하지 않았지만 메모리를 확보한 경우, 0을 리턴하기 위해 i를 계속 돌린다.

        return f(i - 1, r);

    }

 

123에서 메모리를 확보했다면 123은 a에서 값을 갖는다

 

그리고 int b = f(i - 1, r);에서 124로 넘어가게 된다.

 

사실 코드를 잘 살펴보면 순서가 반대인것을 알수잇다

 

정확한 순회 순서는 다음과 같다

 

 

이러한 순서인 것이다.

저작자표시

'알고리즘' 카테고리의 다른 글

백준 13265 : 색칠하기  (0) 2020.05.07
koi & 백준 2638, 2638 : 치즈  (0) 2020.05.05
koi : 최소합  (0) 2020.04.28
백준 2023 : 신기한 소수 & koi 절단 가능 소수  (0) 2020.04.25
koi : 리모콘(dfs, bfs)  (0) 2020.04.24

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

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리

www.acmicpc.net

http://koistudy.net/?mid=prob_page&NO=688&SEARCH=0

 

KOISTUDY

 

koistudy.net

 

 

에라토스테네스로는 해결이 안된다

 

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>
/*
 한 자릿수 중 소수는 2, 3, 5, 7 밖에 없다. 따라서 제일 높은 자릿수의 값은 2, 3, 5, 7만 될 수 있다. 
 (∵오른편 절단 가능 소수이므로)
 
 2. 두 자릿수 이상 넘어가면서 마지막 자릿수 값은 짝수가 될 수 없고(∵2의 배수),
 마찬가지로 5도 될 수 없다(∵5의 배수). 따라서 남는 숫자는 1, 3, 7, 9만 남게 된다. 
 10개의 자릿수를 모두 다 탐색하는 것에 비해 가짓수가 현저히 줄어들게 됨으로 탐색이 빨라진다. (가지치기) 
 
 3. 자릿값을 늘려갈 때 현재 숫자가 소수인지 판별하여 소수인 숫자에만 뒤에 1, 3, 7, 9를 붙여가며 늘려간다. 
 숫자가 커지면 소수 판별에도 시간이 많이 걸리므로 시간을 줄이기 위해 O(sqrt(n))소수 판별 알고리즘을 사용한다.
*/
int n, cnt;
 
int is_prime(int x)
{
    if (x < 2)
    {
        return 0;
    }
    for (int i = 2; i * i <= x; ++i)
    {
        if (x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
 
void func(int num, int len)
{
    if (len == n)
    {
        if (is_prime(num))
        {
            ++cnt;
            std::cout << num << '\n';
        }
        return;
    }
    else
    {
        if (is_prime(num))
        {
            func(num * 10 + 1, len + 1);
            func(num * 10 + 3, len + 1);
            func(num * 10 + 7, len + 1);
            func(num * 10 + 9, len + 1);
        }
    }
}
 
int main()
{
    std::cin >> n;
    func(2, 1);
    func(3, 1);
    func(5, 1);
    func(7, 1);
    //std::cout << cnt;
}
 cs

 

이게 놀라운게 백준은 메모리로 날려버린다지만 koi 저지같은경우 메모리 허용이 되는데, 이 때 에라토스테네스 쓰면 시간초과가 난다.

 

탐색영역의 배제 방식이 dp보다 빠른 경우가 생길수 있다는걸 보여주는 예

 

 

더 괜찮은 소수 판별

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int is_prime(int x)
{
    if (x < 2)
    {
        return 0;
    }
    for (int i = 3; i * i <= x; i += 2)
    {
        if (x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
 cs

x가 2라면 바로 1을 리턴한다.

 

그 외의 경우라면 계산량을 줄일 수 있다

저작자표시

'알고리즘' 카테고리의 다른 글

koi : 앱(small)  (0) 2020.05.01
koi : 최소합  (0) 2020.04.28
koi : 리모콘(dfs, bfs)  (0) 2020.04.24
백준 10971 : 외판원 순회 2 & koi : 연구활동 가는길  (0) 2020.04.24
백준 2615 : 오목  (0) 2020.04.20

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

 

10971번: 외판원 순회 2

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.

www.acmicpc.net

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
 
#include <vector>
 
int arr[11][11];
bool check[11];
int n;
int minimum_dist = 987654321;
 
void input()
{
    std::cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            std::cin >> arr[i][j];
        }
    }
}
 
bool GetAllChk()
{
    for (int i = 1; i <= n; ++i)
    {
        if (check[i] == false)
        {
            return false;
        }
    }
    return true;
}
 
void dfs(int route, int stk, int dist)
{
    if (stk == n - 1)
    {
        if (arr[route][1] != 0)
        {
            if (dist + arr[route][1] < minimum_dist)
            {
                minimum_dist = dist + arr[route][1];
            }
        }
 
        return;
    }
 
    for (int i = 2; i <= n; ++i)
    {
        if (check[i] != true && arr[route][i] != 0)
        {
            check[i] = true;
            dfs(i, stk + 1, dist + arr[route][i]);
            check[i] = false;
        }
    }
}
 
void solve()
{
    dfs(1, 0, 0);
}
 
void output()
{
    if (minimum_dist == 987654321)
    {
        std::cout << 0;
        return;
    }
    std::cout << minimum_dist;
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

http://www.koistudy.net/?mid=prob_page&NO=706&SEARCH=0

 

KOISTUDY

 

www.koistudy.net

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
#include <stdio.h>
 
int n, m, G[11][11], sol = 0x7fffffff, chk[11];
 
void solve(int V, int W)
{
    if (V == n)
    {
        if (W < sol)
        {
            sol = W;
        }
        return;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!chk[i] && G[V][i])
        {
            chk[i] = 1;
            solve(i, W + G[V][i]);
            chk[i] = 0;
        }
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int s, e, w;
        scanf("%d %d %d", &s, &e, &w);
        G[s][e] = G[e][s] = w;
    }
    solve(1, 0);
    printf("%d\n", sol == 0x7fffffff ? -1 : sol);
    return 0;
}
 cs

 

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
#include <iostream>
 
#include <vector>
 
int arr[11][11];
bool check[11];
int n, m;
int minimum_dist = 987654321;
 
void input()
{
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v, val;
        std::cin >> u >> v >> val;
        arr[u][v] = val;
        arr[v][u] = val;
    }
}
 
void dfs(int route, int end, int dist)
{
    if (route == end)
    {
        if (dist < minimum_dist)
        {
            minimum_dist = dist;
        }
 
        return;
    }
 
    for (int i = 1; i <= end; ++i)
    {
        //arr[route][i] 는 항상 값이 0이니 i == route는 필요 없다
        if (i == route || check[i] == true)
        {
            continue;
        }
        if (arr[route][i] != 0)
        {
            check[i] = true;
            dfs(i, end, dist + arr[route][i]);
            check[i] = false;
        }
    }
}
 
void solve()
{
    check[1] = true;
    dfs(1, n, 0);
}
 
void output()
{
    std::cout << minimum_dist;
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

 

방법은 거의 똑같다

저작자표시

'알고리즘' 카테고리의 다른 글

백준 2023 : 신기한 소수 & koi 절단 가능 소수  (0) 2020.04.25
koi : 리모콘(dfs, bfs)  (0) 2020.04.24
백준 2615 : 오목  (0) 2020.04.20
백준 7573 : 고기잡이  (0) 2020.04.20
백준 2622 : 삼각형 만들기  (0) 2020.03.28

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

 

2615번: 오목

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림

www.acmicpc.net

 

 

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
 
int arr[20][20];
int check[4][20][20];
int ans_x, ans_y;
int winner;
 
int dy[5] = { 9999, 1, -1, 0, 1 };
int dx[5] = { 9999, 0, 1, 1, 1 };
 
void input()
{
    for (int i = 1; i < 20; ++i)
        for (int j = 1; j < 20; ++j)
            std::cin >> arr[i][j];
}
void print()
{
    std::cout << '\n';
    for (int y = 1; y < 20; ++y)
    {
        for (int x = 1; x < 20; ++x)
            //std::cout << check[y][x] << ' ';
        std::cout << '\n';
    }
    std::cout << '\n';
}
 
bool find_winner(int y, int x, int elem, int idx, int stk)
{
    while (true)
    {
        if ((19 < y || 19 < x || x < 1 || y < 1) || arr[y][x] != elem)
        {
            break;
        }
 
        check[idx - 1][y][x] = idx;
        y += dy[idx];
        x += dx[idx];
        ++stk;
    }
    if (stk == 5)
    {
        return true;
    }
    return false;
}
 
void solve()
{
    for (int x = 1; x < 20; ++x)
    {
        for (int y = 1; y < 20; ++y)
        {
            if (arr[y][x] == 1)
            {
                for (int i = 1; i <= 4; ++i)
                {
                    if (check[i - 1][y][x] == i)
                    {
                        continue;
                    }
 
                    if (find_winner(y, x, arr[y][x], i, 0))
                    {
                        ans_y = y;
                        ans_x = x;
                        winner = arr[y][x];
                        return;
                    }
                    //print();
                }
            }
        }
    }
}
 
void output()
{
    std::cout << winner << '\n';
    if (winner != 0)
    {
        std::cout << ans_y << ' ' << ans_x;
    }
}
 
int main()
{
 
    input();
    solve();
    output();
 
    return 0;
}
 cs

 

틀린 방법. 6목을 판단하기 위해 굳이 배열을 네개나 더 넣어서 메모리를 뺄 필요가 없이

 

돌을 검사할 때 진행방향 바로 반대에 돌이 있는지만 검사한다면 훨씬 더 효율적인 코드를 짤 수 있다.

 

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
 
int arr[20][20];
int ans_x, ans_y;
int winner;
 
int dy[5] = { 9999, 1, -1, 0, 1 };
int dx[5] = { 9999, 0, 1, 1, 1 };
 
void input()
{
    for (int i = 1; i < 20; ++i)
        for (int j = 1; j < 20; ++j)
            std::cin >> arr[i][j];
}
 
bool find_winner(int y, int x, int elem, int idx, int stk)
{
    while (true)
    {
        if ((19 < y || 19 < x || x < 1 || y < 1) || arr[y][x] != elem)
        {
            break;
        }
 
        y += dy[idx];
        x += dx[idx];
        ++stk;
    }
    if (stk == 5)
    {
        return true;
    }
    return false;
}
 
void solve()
{
    for (int x = 1; x < 20; ++x)
    {
        for (int y = 1; y < 20; ++y)
        {
            if (arr[y][x] != 0)
            {
                for (int i = 1; i <= 4; ++i)
                {
                    if (arr[y - dy[i]][x - dx[i]] == arr[y][x])
                    {
                        continue;
                    }
 
                    if (find_winner(y, x, arr[y][x], i, 0))
                    {
                        ans_y = y;
                        ans_x = x;
                        winner = arr[y][x];
                        return;
                    }
                }
            }
        }
    }
}
 
void output()
{
    std::cout << winner << '\n';
    if (winner != 0)
    {
        std::cout << ans_y << ' ' << ans_x;
    }
}
 
int main()
{
 
    input();
    solve();
    output();
 
    return 0;
}
 cs

 

미련한놈...

저작자표시

'알고리즘' 카테고리의 다른 글

koi : 리모콘(dfs, bfs)  (0) 2020.04.24
백준 10971 : 외판원 순회 2 & koi : 연구활동 가는길  (0) 2020.04.24
백준 7573 : 고기잡이  (0) 2020.04.20
백준 2622 : 삼각형 만들기  (0) 2020.03.28
완전탐색, 전체탐색법  (0) 2020.03.26

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

 

7573번: 고기잡이

한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고기의 수가 줄어들고 있다. 정부에서는 이 문제를 심각하게 생각하여, 물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다. 물고기는 바다 표면 근처에 살기 때문에, 그물의 높이는 중요하지 않다. 따라서 그물은 길이가 l인 직선으로 생각할

www.acmicpc.net

 

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
#include <iostream>
#include <algorithm>
#include <vector>
 
std::vector<std::pair<int, int>> fish;
int N, I, M;
int main()
{
    // 모눈종이의 크기, 그물의 길이, 물고기의 수  N, l, M
    std::cin >> N >> I >> M;
    fish = std::vector<std::pair<int, int>>(M);
    for (int i = 0; i < M; ++i)
    {
        std::cin >> fish[i].first>> fish[i].second;
    }
    int max = 0;
 
    //std::sort(fish.begin(), fish.end());
 
    for (int i = 1; i < I / 2; ++i)
    {
        for (int j = 1; j < I / 2; ++j)
        {
            //그물의 크기
            if (i * 2 + j * 2 == I)
            {
                //물고기 좌표를 찾아감
                for (int idx = 0; idx < fish.size(); ++idx)
                {
 
                    for (int y = fish[idx].first - i; y < fish[idx].first + i; ++y)
                    {
                        for (int x = fish[idx].second - j; x < fish[idx].second + j; ++x)
                        {
                            int cntFish = 0;
 
                            for (int iter = idx; iter < fish.size(); ++iter)
                            {
                                //물고기가 그물의 세로방향 밖에 있으면 continue
                                if(fish[iter].first < y || y + i < fish[iter].first) continue;
                                //물고기가 그물의 가로방향 밖에 있으면 continue
                                if(fish[iter].second < x || x + j < fish[iter].second) continue;
                                ++cntFish;
                            }
 
                            if (cntFish > max) max = cntFish;
                        }
                    }
                }
 
            }
        }
    }
 
    std::cout << max;
    return 0;
}
 cs

 

for i j로 행-열 만 탐색하면 안되고

 

물고기의 좌표를 찾으면 그 좌표에서부터 상하좌우 가능한 모든 그물의 위치를 다 살펴보아야 한다.

 

위의 코드는 효율적인 코드는 아니다. 모든 위치에 대해 살펴보는건 좋으나 필요없는 부분까지 살펴보고 있다. 필요없는 부분을 쳐내면 더 좋을 것임

저작자표시

'알고리즘' 카테고리의 다른 글

백준 10971 : 외판원 순회 2 & koi : 연구활동 가는길  (0) 2020.04.24
백준 2615 : 오목  (0) 2020.04.20
백준 2622 : 삼각형 만들기  (0) 2020.03.28
완전탐색, 전체탐색법  (0) 2020.03.26
백준 2178 : 미로탐색(bfs)  (0) 2020.03.26

+ Recent posts

티스토리툴바