C++ Algorithm/백준 알고리즘 문제 풀이

브루트 포스

3영2 2019. 4. 1. 14:06
반응형

2309번 문제 : 일곱 난쟁이
https://www.acmicpc.net/problem/2309

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>
using namespace std;
 
int main()
{
    int num = 9;
    int sum = 0;
    vector<int> v;
    int a, b;
 
    while (num > 0)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        sum += inp;
        num -- ;
    }
 
    sort(v.begin(), v.end());
 
    bool flag = false;
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (sum - (v.at(i) + v.at(j)) == 100)
            {
                a = i;
                b = j;
                flag = true;
                break;
            }
        }
        if (flag)
            break;
    }
    
    for (int i = 0; i < v.size(); i++)
    {
        if (i == a || i == b)
            continue;
        cout << v.at(i) << endl;
    }
    
    
    return 0;
}
cs


메모:
- 모든 숫자의 합 - 2개의 합 = 100인 숫자 찾음 -> 이 생각을 못하면 문제가 상당히 어려워짐...
- 2개의 합 모든 경우의 수를 for문에 돌려서 찾음
- iterator를 이용해 깔끔하게 erase하고 싶었지만 첫번째 index를 erase하는 순간 값들이 shift하면서 두번째 index값이 바뀜... 그래서 erase하지 못함. 특정 index 여러개를 동시에 erase하는 방법은 없는듯 (remove로는 범위밖에 못함)

2231번 문제 : 분해합

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

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int GetContrustor(int num)
{
    int sum = num;
    while (num > 0)
    {
        sum += num % 10;
        num /= 10;
    }
 
    return sum;
}
 
int main()
{
    int inp;
    cin >> inp;
 
    for (int i = 0; i < inp; i++)
    {
        if (inp == GetContrustor(i))
        {
            cout << i << endl;
            break;
        }
        
        if (i == inp - 1)
            cout << 0 << endl;
    }
 
    return 0;
}
cs


1065번 문제 : 한수
https://www.acmicpc.net/problem/1065

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
#include <iostream>
#include <vector>
 
using namespace std;
 
bool CheckIfSansoo(int n)
{
    if (n < 100)
    {
        return true;
    }
 
    vector<int> v;
 
    while (n > 0)
    {
        int num = n % 10;
        v.push_back(num);
        n /= 10;
    }
    
    int diff = v.at(0) - v.at(1);
    for (int i = 0; i < v.size() - 1; i++)
    {
        int temp = v.at(i) - v.at(i + 1);
        if (diff != temp)
            return false;
    }
    return true;
 
}
 
int main()
{
    int inp;
    cin >> inp;
    int num = 0;
 
    for (int i = 1; i <= inp; i++)
    {
        if (CheckIfSansoo(i))
            num++;
    }
 
    cout << num;
 
    return 0;
}
 
cs


1038번 문제 : 감소하는 수
https://www.acmicpc.net/problem/7568

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
#include <iostream>
#include <vector>
using namespace std;
 
struct PersonInfo
{
    int weight;
    int height;
    int ranking;
};
 
int main()
{
    int num;
    cin >> num;
 
    vector<PersonInfo> v;
 
    while (num > 0)
    {
        int inpA, inpB;
        cin >> inpA >> inpB;
        v.push_back({ inpA, inpB, 1 });
        num--;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (v.at(i).height < v.at(j).height && v.at(i).weight < v.at(j).weight)
                v.at(i).ranking++;
        }
    }
 
    for (auto i : v)
        cout << i.ranking << " ";
 
    return 0;
}
 
cs

1038번 문제 : 감소하는 수
https://www.acmicpc.net/problem/1038

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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    int inp;
    cin >> inp;
    vector<long long> v;
 
    for (int i = 0; i <= 9; i++)
    {
        int vSize = v.size();
        //v.size() should not be used due to the change of the size changing after pushing back the result inside a loop
        for (int j = 0; j < vSize; j++) 
        {
            string result = to_string(i) + to_string(v.at(j));
            v.push_back(stoll(result)); //stoi -> int       stol -> long       stoll -> long long
        }
        v.push_back(i);
    }
    sort(v.begin(), v.end());
 
    if (v.size() > inp)
        cout << v.at(inp) << endl;
    else
        cout << -1 << endl;
 
    return 0;
}
cs


메모:
-규칙을 찾으면 0 / 10, 1, 0 / 210 21, 20, 2, 10, 1, 0 / 3210, 321, 320 ,32, 310 , 31, 30, 3 ....
-루프문에 동적배열인 vector.size() (벡터 크기) 기준으로 루프가 돌때 루프안에서 vector를 push하거나 erase, remove하면 size()가 변하기 때문에 이를 감안하면서 코드를 짜야함
-문자열을 int, long, long long로 변환할때: stoi -> int       stol -> long       stoll -> long long (c++11이상)






반응형
저작자표시