Loading [MathJax]/jax/output/CommonHTML/jax.js
반응형

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

 

11311번: Jug Hard

The first line contains T, the number of test cases (1 ≤ T 100 000). Each test case is composed of three integers: a b d where a and b (1 ≤ a, b ≤ 10 000 000) are the volumes of the two jugs, and d is the desired volume of water to be generated. You

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. a, b, d를 입력받고, d는 무조건 a 또는 b보다 작아야 d를 만들 수 있으므로 a >= d || b >= d인지 확인합니다.

 

2. a와 b를 이용해 만들 수 있는 수는 a와 b의 최대 공약수의 배수이면서 a와 b 중 더 큰 값보다 작거나 같은 수이므로 d가 a와 b의 최대공약수의 배수이면 Yes를 아니라면 No를 출력합니다. 

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T;
int a, b, d;
 
int euclid(int a, int b)
{
    while (b) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
 
    return a;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> a >> b >> d;
 
        if (a >= d || b >= d) {
            int tmp = euclid(a, b);
 
            if (d % tmp == 0) {
                cout << "Yes";
            }
            else{
                cout << "No";
            }
        }
        else {
            cout << "No";
        }
 
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14881번 - 물통 문제 (C++)  (0) 2023.10.25
[ 백준 ] 20917번 - 사회적 거리 두기 (C++)  (0) 2023.10.24
[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
반응형

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

 

14881번: 물통 문제

용량이 a, b 리터인 두 물통이 있다. 이때, 물을 적절히 부어서 정확하게 c리터를 만들 수 있는지 아닌지 구하는 프로그램을 작성하시오. 물은 무한히 많다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. a, b, c를 입력받고, c는 무조건 a 또는 b보다 작아야 c를 만들 수 있으므로 a >= c || b >= c인지 확인합니다.

 

2. a와 b를 이용해 만들 수 있는 수는 a와 b의 최대 공약수의 배수이면서 a와 b 중 더 큰 값보다 작거나 같은 수이므로 c가 a와 b의 최대공약수의 배수이면 YES를 아니라면 NO를 출력합니다. 

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T;
int a, b, c;
 
int euclid(int a, int b)
{
    while (b) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
 
    return a;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> a >> b >> c;
 
        if (a >= c || b >= c) {
            int tmp = euclid(a, b);
 
            if (c % tmp == 0) {
                cout << "YES";
            }
            else{
                cout << "NO";
            }
        }
        else {
            cout << "NO";
        }
 
        cout << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11311번 - Jug Hard (C++)  (0) 2023.10.26
[ 백준 ] 20917번 - 사회적 거리 두기 (C++)  (0) 2023.10.24
[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
반응형

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

 

20917번: 사회적 거리 두기

Albert는 L대학에서 주최하는 Hackathon 행사 진행을 도와주기로 했는데, 사회적 거리 두기 방침에 따라 모든 참가자들을 최대한 멀리 떨어트려 좌석 배정을 해주려 한다. 이를 위해 아주 길다란 복

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. n과 s를 입력받고, vector<int> arr에 콘센트 좌표를 저장합니다.

 

2. arr를 오름차순으로 정렬하고, a = 0, b = 1,000,000,000으로 저장한 후 매개변수 탐색을 실시합니다.

 

3. m = (a + b) / 2를 통해 m을 갱신하고, tmp = arr[ 0 ], cnt = 1로 시작하여 이분 탐색을 이용해 다음 콘센트의 위치를 찾습니다. < lower_bound(arr.begin(), arr.end(), tmp + m) >

 

4. 다음 콘센트의 위치가 범위를 벗어나지 않으면 cnt++를 해주고, cnt의 값이 s보다 크거나 같으면 true를 반환하고, 그렇지 않다면 false를 반환합니다.

 

5. true를 반환받으면 ans = m 후 a = m + 1로 갱신해 주고, false를 반환받으면 b = m으로 갱신해 주고 매개변수탐색을 계속 진행합니다.

 

6. a < b일 때까지 계속 반복해 준 후 ans를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int T;
int n, s;
vector<int> arr;
 
bool check(int m)
{
    int tmp = arr[0];
    int cnt = 1;
    while (1) {
        auto it = lower_bound(arr.begin(), arr.end(), tmp + m);
        if (it == arr.end()) break;
        tmp = *it;
        cnt++;
    }
 
    if (cnt >= s) return true;
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> n >> s;
 
        arr.clear();
 
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            arr.push_back(num);
        }
 
        sort(arr.begin(), arr.end());
 
        int a, b;
        a = 0;
        b = 1000000000;
        int ans = 0;
 
        while (a < b) {
            int m = (a + b) / 2;
 
            if (check(m)) {
                ans = m;
                a = m + 1;
            }
            else {
                b = m;
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11311번 - Jug Hard (C++)  (0) 2023.10.26
[ 백준 ] 14881번 - 물통 문제 (C++)  (0) 2023.10.25
[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
반응형

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

 

1132번: 합

N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 문자열을 입력받고, 각 알파벳에 따라 자릿수를 arr 배열에 저장하고, 첫 자리에 오는지 오지 않는지 isFirst 배열에 저장합니다.

 

2. arr 배열을 내림차순으로 정렬하고, 만약 가장 작은 자릿수의 숫자가 첫번째 수라면 0이 오면 안 되기 때문에 첫 자리에 오는 수가 없는 알파벳과 교환합니다.

 

3. arr 배열을 내림차순으로 0부터 8번 인덱스까지만 정렬합니다.

 

4. arr 배열을 0부터 9까지 for문을 이용하여 돌면서 0번 인덱스일 경우 9를 곱해주고, 1번 인덱스일 경우 8을 곱해주면서 9번 인덱스까지 ans에 더해줍니다.

 

5. ans를 출력합니다.

 

[ 소스코드 ]

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<string>
#include<cmath>
#define ll long long
 
using namespace std;
 
int N;
pair<ll,int> arr[26];
bool isFirst[26];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < 26; i++) {
        arr[i].second = i;
    }
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        isFirst[str[0] - 'A'] = true;
 
        for (int j = 0; j < str.size(); j++) {
            arr[str[j] - 'A'].first += pow(10, str.size() - j - 1);
        }
    }
 
    sort(arr, arr + 26, greater<>());
 
    if (isFirst[arr[9].second]) {
        for (int i = 8; i >= 0; i--) {
            if (isFirst[arr[i].second] == false) {
                swap(arr[9], arr[i]);
                break;
            }
        }
    }
 
    sort(arr, arr + 9, greater<>());
 
    ll ans = 0;
    int cnt = 9;
 
    for (int i = 0; i < 10; i++) {
        ans += arr[i].first * cnt--;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14881번 - 물통 문제 (C++)  (0) 2023.10.25
[ 백준 ] 20917번 - 사회적 거리 두기 (C++)  (0) 2023.10.24
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
반응형

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

 

4395번: Steps

One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step. What is the minimum number of steps in order to get from x to y

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. x와 y를 입력받고, dif = y - x로 갱신합니다.

 

2. tmp = (int)sqrt(dif)로 갱신하고, ans = tmp * 2 - 1로 갱신합니다. (1 + 2 + 3 + 2 + 1 = 9, 1 + 2 + 3 + 4 + 3 + 2 + 1 = 16)

 

3. tmp * tmp < dif 라면 ans++를 해주고, tmp + 0.5 < sqrt(dif) 라면 ans++ 해줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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<cmath>
 
using namespace std;
 
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    while (n--) {
        int x, y;
        cin >> x >> y;
 
        int dif = y - x;
        int tmp = (int)sqrt(dif);
 
        int ans = tmp * 2 - 1;
 
        if (dif == 0) {
            cout << 0 << '\n';
        }
        else {
            if (dif - tmp * tmp != 0) {
                ans++;
                if ((double)tmp + 0.5f < sqrt(dif)) {
                    ans++;
                }
            }
 
            cout << ans << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 20917번 - 사회적 거리 두기 (C++)  (0) 2023.10.24
[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
반응형

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

 

17433번: 신비로운 수

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있고, 첫째 줄에 N, 둘째 줄에 N개의 정수가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받은 수들을 정렬하고, 인접한 수들의 차를 dif 배열에 저장합니다.

 

2. dif 배열의 인접한 수들끼리 유클리드 호제법을 사용하여 최대 공약수를 ans에 저장합니다.

 

3. ans가 0이라면 INFINITY를 출력하고, 그렇지 않다면 ans를 출력합니다. 

 

[ 소스코드 ]

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>
 
using namespace std;
 
int arr[2000];
int dif[2000];
int T, N;
int ans;
 
int euclid(int a, int b)
{
    while (b) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
 
    return a;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
 
        sort(arr, arr + N);
 
        for (int i = 0; i < N - 1; i++) {
            dif[i] = arr[i + 1] - arr[i];
        }
 
        ans = dif[0];
 
        for (int i = 1; i < N - 1; i++) {
            ans = euclid(ans, dif[i]);
        }
 
        if (ans == 0) {
            cout << "INFINITY\n";
        }
        else {
            cout << ans << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1132번 - 합 (C++)  (0) 2023.10.23
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
반응형

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

 

1684번: 같은 나머지

첫째 줄에 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 절댓값이 1,000,000을 넘지 않는 n개의 정수들이 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받은 수들을 정렬하고, 인접한 수들의 차를 dif 배열에 저장합니다.

 

2. dif 배열의 인접한 수들끼리 유클리드 호제법을 사용하여 최대 공약수를 ans에 저장합니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int n;
int arr[1000];
int dif[1000];
int ans;
 
int euclid(int a, int b)
{
    while (b) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
 
    return a;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    for (int i = 0; i < n - 1; i++) {
        dif[i] = arr[i + 1] - arr[i];
    }
 
    ans = dif[0];
 
    for (int i = 1; i < n - 1; i++) {
        ans = euclid(ans, dif[i]);
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
반응형

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

 

11578번: 팀원 모집

3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 1부터 2M - 1까지 for문을 이용해 돌면서 해당 비트가 1이라면 해당 팀원이 풀 수 있는 문제들을 풀고, cnt++를 해준 후 모든 문제를 풀었다면 가장 낮은 cnt를 ans에 저장해 줍니다.

 

2. ans가 갱신되지 않았다면 -1을 출력하고 그렇지 않다면 ans를 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<cmath>
 
using namespace std;
 
int N, M;
vector<int> list[11];
int ans = 987654321;
int mask;
 
void check(int num)
{
    int tmp = 0;
    int cnt = 0;
    for (int i = 0; i < M; i++) {
        if (num & 1 << i) {
            for (auto& next : list[i]) {
                tmp |= 1 << next;
            }
            cnt++;
        }
    }
 
    if (tmp == mask) {
        ans = min(ans, cnt);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int n;
        cin >> n;
 
        for (int j = 0; j < n; j++) {
            int tmp;
            cin >> tmp;
            list[i].push_back(tmp);
        }
    }
 
    mask = pow(2, N + 1) - 2;
    
    for (int i = 1; i < pow(2, M); i++) {
        check(i);
    }
 
    if (ans == 987654321) cout << -1;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
반응형

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

 

19591번: 독특한 계산기

숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열을 입력받을 str 변수를 선언하고, 입력을 받습니다.

 

2. num을 선언하고, 기호가 아닌 문자가 나오면 num = num * 10 + str[ i ] - '0'을 통해 num을 갱신해 줍니다.

 

3. 기호가 나온다면 deque<char> symbol에 기호를 push_back 해주고, 첫 번째 문자열이 '-'라면 isFirst를 true로 바꾸고, num의 값에 -1을 곱해준 후 deque<ll> number에 num을 push_back 해줍니다.

 

4. 이후 규칙에 맞게 계산을 하고, 답을 출력합니다.

 

[ 소스 코드 ]

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<iostream>
#include<deque>
#include<string>
#define ll long long
 
using namespace std;
deque<ll> number;
deque<char> symbol;
ll ans;
 
ll cal(ll num1, ll num2, char sym)
{
    if (sym == '+') {
        return num1 + num2;
    }
    else if (sym == '-') {
        return num1 - num2;
    }
    else if (sym == '*') {
        return num1 * num2;
    }
    else {
        return num1 / num2;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string str;
 
    cin >> str;
 
    bool isFirst = false;
    ll num = 0;
 
    for (int i = 0; i < str.size(); i++) {
        if (i == 0 && str[i] == '-') {
            isFirst = true;
        }
        else if (str[i] >= '0') {
            num = num * 10 + str[i] - '0';
        }
        else {
            if (isFirst) {
                isFirst = false;
                num *= -1;
            }
            number.push_back(num);
            symbol.push_back(str[i]);
            num = 0;
        }
    }
    if (isFirst) {
        isFirst = false;
        num *= -1;
    }
    number.push_back(num);
 
    if (number.size() == 1) {
        cout << number.front();
        return 0;
    }
 
    while (1) {
        ll tmp[4] = { 0 };
 
        if (number.size() == 3) {
            tmp[0] = number.front();
            tmp[3] = number.back();
            number.pop_back();
            number.pop_front();
            tmp[1] = tmp[2] = number.front();
        }
        else if (number.size() == 2) {
            tmp[0] = number.front();
            tmp[1] = number.back();
        }
        else {
            tmp[0] = number.front();
            tmp[3] = number.back();
            number.pop_back();
            number.pop_front();
            tmp[1] = number.front();
            tmp[2] = number.back();
        }
 
        if (symbol.size() == 1) {
            char sym = symbol.front();
            cout << cal(tmp[0], tmp[1], sym);
 
            return 0;
        }
        else {
            char sym1 = symbol.front();
            char sym2 = symbol.back();
 
            if (sym1 == '+' || sym1 == '-') {
                if (sym2 == '*' || sym2 == '/') {
                    symbol.pop_back();
                    number.pop_back();
                    number.push_back(cal(tmp[2], tmp[3], sym2));
                    number.push_front(tmp[0]);
                }
                else {
                    ll num1 = cal(tmp[0], tmp[1], sym1);
                    ll num2 = cal(tmp[2], tmp[3], sym2);
 
                    if (num1 >= num2) {
                        symbol.pop_front();
                        number.pop_front();
                        number.push_front(cal(tmp[0], tmp[1], sym1));
                        number.push_back(tmp[3]);
                    }
                    else {
                        symbol.pop_back();
                        number.pop_back();
                        number.push_back(cal(tmp[2], tmp[3], sym2));
                        number.push_front(tmp[0]);
                    }
                }
            }
            else if (sym1 == '*' || sym1 == '/') {
                if (sym2 == '+' || sym2 == '-') {
                    symbol.pop_front();
                    number.pop_front();
                    number.push_front(cal(tmp[0], tmp[1], sym1));
                    number.push_back(tmp[3]);
                }
                else {
                    ll num1 = cal(tmp[0], tmp[1], sym1);
                    ll num2 = cal(tmp[2], tmp[3], sym2);
 
                    if (num1 >= num2) {
                        symbol.pop_front();
                        number.pop_front();
                        number.push_front(cal(tmp[0], tmp[1], sym1));
                        number.push_back(tmp[3]);
                    }
                    else {
                        symbol.pop_back();
                        number.pop_back();
                        number.push_back(cal(tmp[2], tmp[3], sym2));
                        number.push_front(tmp[0]);
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
반응형

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

 

14699번: 관악산 등산

서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ 5001 ]을 선언하고 -1로 초기화해 줍니다.

 

2. 1번 노드부터 N번 노드까지 dfs를 돌면서 갈 수 있는 쉼터의 최댓값을 다음의 점화식을 이용하여 dp[ i ]에 저장합니다.

dp[ i ] = max( dp[ i ], dfs(next) + 1 )

 

3. 1번 노드부터 N번 노드까지 dfs( i )를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int N, M;
int H[5001];
int dp[5001];
vector<int> list[5001];
 
int dfs(int cur)
{
    if (dp[cur] != -1) return dp[cur];
    int& ret = dp[cur];
    ret = 1;
 
    for (auto& next : list[cur]) {
        if (H[cur] < H[next]) {
            ret = max(ret, dfs(next) + 1);
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
        dp[i] = -1;
    }
 
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    for (int i = 1; i <= N; i++) {
        cout << dfs(i) << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11578번 - 팀원 모집 (C++)  (1) 2023.10.19
[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++)  (0) 2023.10.16
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14

+ Recent posts

티스토리툴바