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

 

1094번: 막대기

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대��

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
#include <iostream>
 
bool binaryArr[8];
int X, ans;
 
void input()
{
    std::cin >> X;
}
 
void solve(int stk, int up, int down)
{
    int mid = up + (down - up) / 2;
    if (mid == X || down == X)
    {
        ans = stk;
        return;
    }
    else if (mid < X)
    {
        solve(stk + 1, mid + 1, down);
    }
    else if (mid > X)
    {
        solve(stk + 1, up, mid - 1);
    }
}
 
void binary_solve()
{
    int i = 1;
    while (X != 0)
    {
        binaryArr[i++] = X % 2;
        X /= 2;
    }
    for (int i = 1; i < 8; ++i)
    {
        if (binaryArr[i])
        {
            ++ans;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    //solve(1, 1, 64);
    binary_solve();
    output();
    return 0;
}
 cs

 

첨엔 이분탐색 아녀?? 했다가

 

아차차

 

33같은 경우엔 32cm 막대 하나랑 1cm 막대 하나가 필요하다

 

헌데 막대를 자르는 기준은 절반으로 나누는 것이고

 

최대 막대 길이는 64이다

 

64 32 16 8 4 2 1

 

아하!

저작자표시

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

백준 9517 : 아이 러브 크로아티아  (0) 2020.07.21
백준 14890 : 경사로  (0) 2020.07.17
백준 2455 : 지능형 기차  (0) 2020.07.16
백준 14889 : 스타트와 링크  (0) 2020.07.15
koi : 선물(M)  (0) 2020.07.14

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

 

2455번: 지능형 기차

최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. �

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
#include <iostream>
 
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
class train_simulator
{
public:
    void get_in(unsigned int passingers)
    {
        _passingers += passingers;
        _compMaximum();
    }
    void get_out(unsigned int passingers)
    {
        _passingers -= passingers;
    }
    unsigned int get_maximum_passingers()
    {
        return _maximumPassingersPerDay;
    }
private:
    void _compMaximum()
    {
        _maximumPassingersPerDay = _maximumPassingersPerDay < _passingers ? _passingers : _maximumPassingersPerDay;
    }
private:
    unsigned int _passingers = 0;
    unsigned int _maximumPassingersPerDay = 0;
};
 
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
void input(train_simulator& myTrain)
{
    unsigned int passingers_in, passingers_out;
    do
    {
        std::cin >> passingers_out >> passingers_in;
        myTrain.get_out(passingers_out);
        myTrain.get_in(passingers_in);
    } while (passingers_in != 0);
}
 
void output(train_simulator& ans)
{
    std::cout << ans.get_maximum_passingers();
}
 
int main()
{
    train_simulator myTrain;
    input(myTrain);
    output(myTrain);
    return 0;
}
 cs

 

뿌뿌~~~~칙칙폭폭칙칙폭폭칙칙폭폭칙칙폭폭

저작자표시

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

백준 14890 : 경사로  (0) 2020.07.17
백준 1094 : 막대기  (0) 2020.07.16
백준 14889 : 스타트와 링크  (0) 2020.07.15
koi : 선물(M)  (0) 2020.07.14
koi : 경찰차(M)  (0) 2020.07.14

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

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
#include <iostream>
 
int n, ans = 987654321;
int team[21][21];
bool visited[21];
 
void input()
{
    std::cin >> n;
    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < n; ++x)
        {
            std::cin >> team[y][x];
        }
    }
}
 
int chk(bool flag)
{
    int rest = 0;
    for (int y = 0; y < n; ++y)
    {
        if (visited[y] == flag)
        {
            for (int x = y; x < n; ++x)
            {
                if (visited[x] == flag)
                {
                    rest += team[y][x] + team[x][y];
                }
            }
        }
    }
    return rest;
}
// 0 3 4
// 2 0 4
// 2 4 0
// 19
// 0 2 5
// 1 0 5
// 1 3 0
// 17
void solve(int stk, int fSum, int pivot)
{
    if (stk == n / 2)
    {
        int temp = chk(false);
        int cmpTemp = abs(temp - fSum);
 
        if (cmpTemp < ans)
        {
            ans = cmpTemp;
        }
        return;
    }
 
    for (int i = pivot; i < n; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            int temp = 0;
            for (int j = 0; j < i; ++j)
            {
                if (visited[j])
                {
                    temp += team[i][j] + team[j][i];
                }
            }
            solve(stk + 1, fSum + temp, i);
            visited[i] = false;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve(0, 0, 0);
    output();
    return 0;
}
 cs

 

완전탐색이지만, 중복에 대한 검사를 어느정도는 해 줘야 풀린다.

 

사실 fSum이 크게 필요는 없었던 것이 아닐까?

 

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
int chk(bool flag)
{
    int rest = 0;
    for (int y = 0; y < n; ++y)
    {
        if (visited[y] == flag)
        {
            for (int x = y; x < n; ++x)
            {
                if (visited[x] == flag)
                {
                    rest += team[y][x] + team[x][y];
                }
            }
        }
    }
    return rest;
}
 
void solve(int stk, int fSum, int pivot)
{
    if (stk == n / 2)
    {
        int temp = chk(false);
        int fff = chk(true);            //변경!
        int cmpTemp = abs(temp - fff);    //변경!
 
        if (cmpTemp < ans)
        {
            ans = cmpTemp;
        }
        return;
    }
 
    for (int i = pivot; i < n; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            /*int temp = 0;
            for (int j = 0; j < i; ++j)
            {
                if (visited[j])
                {
                    temp += team[i][j] + team[j][i];
                }
            }*/
            solve(stk + 1, fSum, i);
            visited[i] = false;
        }
    }
}
 cs

그것은 팩트였구요

 

하지만 기존에 비해 좀 더 느리다.

 

중요한 점은 dfs 탐색 시 중복값을 얼마나 잘 걸러내느냐

 

모든 배열에 대해 탐색할 필요는 없다

 

이렇게만 탐색해도 충분하다

저작자표시

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

백준 1094 : 막대기  (0) 2020.07.16
백준 2455 : 지능형 기차  (0) 2020.07.16
koi : 선물(M)  (0) 2020.07.14
koi : 경찰차(M)  (0) 2020.07.14
koi : 거스름 돈(M)  (0) 2020.07.14

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

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
#include <iostream>
#include <stack>
#include <queue>
 
bool mat[1010][1010];
bool visited[1010];
int n, m, v;
 
void input()
{
    std::cin >> n >> m >> v;
    for (int y = 0; y < m; ++y)
    {
        int from, to;
        std::cin >> from >> to;
        mat[from][to] = true;
        mat[to][from] = true;
    }
}
 
void dfs()
{
    std::stack<int> dfs;
    dfs.push(v);
    while (dfs.empty() == false)
    {
        int currPos = dfs.top();
        dfs.pop();
        if (visited[currPos] == true)
        {
            continue;
        }
        visited[currPos] = true;
        
        std::cout << currPos << ' ';
        for (int x = 1000; x > 0; --x)
        {
            if (mat[currPos][x] == true && visited[x] == false)
            {
                dfs.push(x);
            }
        }
    }
    std::cout << '\n';
}
 
void bfs()
{
    std::queue<int> bfs;
    bfs.push(v);
    while (bfs.empty() == false)
    {
        int currPos = bfs.front();
        bfs.pop();
        if (visited[currPos] == true)
        {
            continue;
        }
        visited[currPos] = true;
 
        std::cout << currPos << ' ';
        for (int x = 1; x <= 1000; ++x)
        {
            if (mat[currPos][x] == true && visited[x] == false)
            {
                bfs.push(x);
            }
        }
    }
}
 
void solve()
{
    dfs();
    for (int i = 0; i < 1010; ++i)
    {
        visited[i] = false;
    }
    bfs();
}
 
void output()
{
 
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

 

벡터로 가지 않으면 시간초과가 날까 조마조마했지만

 

별 상관은 없었다

 

그러니 다시한번 기억하자 dfs는 스택, bfs는 큐

저작자표시

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

koi : 경찰차(M)  (0) 2020.07.14
koi : 거스름 돈(M)  (0) 2020.07.14
koi : minimum sum(M)  (0) 2020.06.26
koi : 연구활동 가는 길(L)  (0) 2020.06.26
koi : 저울 추(L)  (0) 2020.06.26

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

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는

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
#include <iostream>
#include <vector>
#include <algorithm>
 
int k = 0;
std::vector<int> vec, lotto;
int ans = 0;
 
bool input()
{
    ans = 0;
    int input;
    vec.clear();
    lotto.clear();
    std::cin >> k;
    for (int i = 0; i < k; ++i)
    {
        std::cin >> input;
        vec.push_back(input);
    }
    return k;
}
 
void solve()
{
    lotto = { 0, 0, 0, 0, 0, 0 };
    for (int i = 0; i < k - 6; ++i)
    {
        lotto.push_back(1);
    }
    //std::sort(lotto.begin(), lotto.end());
    do 
    {
        for (int i = 0; i < k; ++i)
        {
            if (lotto[i] == 0)
            {
                std::cout << vec[i] << ' ';
            }
        }
        std::cout << '\n';
    } while (std::next_permutation(lotto.begin(), lotto.end()));
    std::cout << '\n';
}
 
int main()
{
    while (input())
    {
        solve();
    }
    return 0;
}
 cs

 

재귀를 쓰지는 않았고, next_permutation 사용했다

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    std::vector<int> tmp1 = { 1, 2, 3 };
    std::vector<int> tmp2 = { 0, 0, 1 };
    do 
    {
        for (auto& it : tmp1)
        {
            std::cout << it << ' ';
        }
        std::cout << '\n';
    } while (std::next_permutation(tmp1.begin(), tmp1.end()));
    std::cout << "-------------------------------------------------\n";
    do
    {
        for (auto& it : tmp2)
        {
            std::cout << it << ' ';
        }
        std::cout << '\n';
    } while (std::next_permutation(tmp2.begin(), tmp2.end()));
 cs

원리는 다음과 같다

같은 숫자가 존재한다면 빼버린다

 

a b c

0 0 1

 

b a c

0 0 1

 

이러한 경우는 한번만 출력

 

즉

 

a b

a c

b c

를 출력하면서 3개의 숫자 중 2개의 숫자를 뽑는 조합인 것

 

결론은 next_permutation을 이용한 조합의 구현.

저작자표시

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

koi : 연구활동 가는 길(L)  (0) 2020.06.26
koi : 저울 추(L)  (0) 2020.06.26
백준 14888 : 연산자 끼워넣기  (0) 2020.06.23
백준 14502 : 연구소 (브루트포스)  (0) 2020.06.19
백준 17478 : 재귀함수가 뭔가요?  (0) 2020.06.19

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

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, ��

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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
 
int n;
long long maxi = -987654321, mini = 987654321;
std::vector<int> oper;
std::vector<int> vec;
 
void input()
{
    int input;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> input;
        vec.push_back(input);
    }
    std::cin >> input;
    oper.insert(oper.end(), input, 1);
    std::cin >> input;
    oper.insert(oper.end(), input, 2);
    std::cin >> input;
    oper.insert(oper.end(), input, 3);
    std::cin >> input;
    oper.insert(oper.end(), input, 4);
}
 
void solve()
{
 
    do 
    {
        int sum = vec[0];
        for (int i = 0; i < oper.size(); ++i)
        {
            if (oper[i] == 1)
            {
                sum += vec[i + 1];
            }
            else if (oper[i] == 2)
            {
                sum -= vec[i + 1];
            }
            else if (oper[i] == 3)
            {
                sum *= vec[i + 1];
            }
            else
            {
                sum /= vec[i + 1];
            }
        }
        maxi = maxi < sum ? sum : maxi;
        mini = mini > sum ? sum : mini;
    } while (std::next_permutation(oper.begin(), oper.end()));
    std::cout << maxi << '\n' << mini << std::endl;
}
 
int main()
{
    input();
    solve();
}
 cs

 

왜 연산자 입력을 저렇게 했냐면

 

stl 연습이라고 해야할까ㅎ

 

해당 조건에 따라 나눗셈 연산을 제대로 해본다면

 

1
2
3
4
5
6
7
8
9
10
11
12
13
sum = sum < 0 ? -((-sum) / vec[i + 1] ) : sum / vec[i + 1];
 
풀어서 쓰자면
if(sum < 0)
{
    sum = -sum;            //음수를 양수로 바꾸고(절댓값)
    sum /= vec[i + 1]     //바꾼 양수를 나눠서
    sum = -sum;            //다시 음수로 바꾼다.
}
else
{
    sum /= vec[i + 1];
}
 cs

 

저작자표시

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

koi : 저울 추(L)  (0) 2020.06.26
백준 6603 : 로또  (0) 2020.06.23
백준 14502 : 연구소 (브루트포스)  (0) 2020.06.19
백준 17478 : 재귀함수가 뭔가요?  (0) 2020.06.19
탐색공간의 배제  (0) 2020.06.18

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크�

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <vector>
 
int n, m;
int lab[10][10];
int myLab[10][10];
std::vector<std::pair<int, int>> covid19;
int ans = 0;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
void print()
{
    std::cout << '\n';
    for (int y = 0; y <= n + 1; ++y)
    {
        for (int x = 0; x <= m + 1; ++x)
        {
            std::cout << myLab[y][x] << ' ';
        }
        std::cout << '\n';
    }
    std::cout << "------------------------------------\n";
}
 
void input()
{
    std::cin >> n >> m;
    for (int y = 1; y <= n; ++y)
    {
        for (int x = 1; x <= m; ++x)
        {
            std::cin >> lab[y][x];
            if (lab[y][x] == 2)
            {
                covid19.push_back(std::pair<int, int>({ y, x }));
            }
            myLab[y][x] = lab[y][x];
        }
    }
}
 
void ff(int y, int x)
{
    if (y < 1 || n < y || x < 1 || m < x)
    {
        return;
    }
    
    myLab[y][x] = 2;
    for (int i = 0; i < 4; ++i)
    {
        if (myLab[y + dy[i]][x + dx[i]] == 0)
        {
            ff(y + dy[i], x + dx[i]);
        }
    }
}
 
void clear()
{
    for (int y = 1; y <= n; ++y)
    {
        for (int x = 1; x <= m; ++x)
        {
            if (myLab[y][x] == 2)
            {
                myLab[y][x] = 0;
            }
        }
    }
    
    for (auto& it : covid19)
    {
        myLab[it.first][it.second] = 2;
    }
}
 
void solve(int stk)
{
    if (stk == 3)
    {
        //바이러스 플러드필
        for (auto& it : covid19)
        {
            ff(it.first, it.second);
        }
        //print();
 
        //남은 0 체크
        int safety = 0;
        for (int y = 1; y <= n; ++y)
        {
            for (int x = 1; x <= m; ++x)
            {
                if (myLab[y][x] == 0)
                {
                    ++safety;
                }
            }
        }
 
        ans = ans < safety ? safety : ans;
        clear();
        //print();
        return;
    }
    //모든 0에 벽 3개 설치
    for (int y = 1; y <= n; ++y)
    {
        for (int x = 1; x <= m; ++x)
        {
            if (myLab[y][x] == 0)
            {
                myLab[y][x] = 1;
                //print();
                solve(stk + 1);
                myLab[y][x] = 0;
            }
        }
    }
 
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve(0);
    output();
    return 0;
}
 cs

 

가로세로 바꿔써서 삽질한건 안자랑

저작자표시

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

백준 6603 : 로또  (0) 2020.06.23
백준 14888 : 연산자 끼워넣기  (0) 2020.06.23
백준 17478 : 재귀함수가 뭔가요?  (0) 2020.06.19
탐색공간의 배제  (0) 2020.06.18
백준 14501 : 퇴사  (0) 2020.06.18

+ Recent posts

티스토리툴바