반응형

문제 링크: https://www.acmicpc.net/problem/17521

 

17521번: Byte Coin

입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나

www.acmicpc.net

<문제 풀이> 그리디 알고리즘

 

다음 날에 가격이 증가하면 코인을 모두 매수하고, 감소하면 코인을 모두 매도하면 됩니다.

 

<C++소스코드>

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
#include<iostream>
using namespace std;
 
typedef long long ll;
ll n, w;
ll price[16];
void input() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) cin >> price[i];
}
 
void solve() {
    input();
    ll cur = price[1];
    ll coin = 0;
    for (int i = 2; i <= n; i++) {
        int next = price[i];
        if (next > cur) { // 다음 날에 가격이 증가하면
            coin += w / cur; // 최대한 코인을 매수한다.
            w %= cur;
        }
        else if (next < cur) { // 감소하면
            w += coin * cur;// 코인을 모두 매도한다.
            coin = 0;
        }
        cur = next;
    }
    w += coin * cur; // 마지막 날 코인을 모두 매도한다.
    cout << w;
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}
 cs
 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2056번] 작업  (0) 2023.09.01
[백준 2283] 구간 자르기  (0) 2023.08.30
[백준 1439번] 뒤집기  (0) 2023.04.23
[백준 20365번] 블로그2  (0) 2023.04.23
[백준 20115번] 에너지 드링크  (0) 2023.04.22
반응형

문제 링크: https://www.acmicpc.net/problem/1439 

 

1439번: 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모

www.acmicpc.net

<문제 풀이> 그리디 알고리즘

 

연속된 숫자를 한 번에 뒤집을 수 있기 때문에, 먼저 연속된 숫자들을 하나로 합쳐줍니다.

그리고 남은 숫자들 중에서 개수가 더 적은 숫자를 하나씩 뒤집어주면 됩니다.

 

0001100

-> 010

-> 000 (1번)

 

<C++소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    string s; cin >> s;
    char c = s[0];
    for (int i = 1; i < s.length(); i++) {
        if (c == s[i])s[i] = '.';
        else {
            c = s[i];
        }
    }
    int zero = count(s.begin(), s.end(), '0');
    int one = count(s.begin(), s.end(), '1');
    cout << min(zero, one);
    return 0;
}
cs
 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2283] 구간 자르기  (0) 2023.08.30
[백준 17521번] Byte Coin  (0) 2023.04.24
[백준 20365번] 블로그2  (0) 2023.04.23
[백준 20115번] 에너지 드링크  (0) 2023.04.22
[백준 1343번] 폴리오미노  (0) 2023.04.22
반응형

문제 링크: 

<문제 풀이> 그리디 알고리즘

 

연속된 색은 한 번에 칠할 수 있기 때문에, 이를 하나의 색으로 만들어줍니다.

그다음 가장 많은 개수의 색으로 전체를 먼저 칠한 후 나머지 색으로 하나씩 칠하면 됩니다.

 

BBRBRBBR

-> BRBRBR

-> BBBBBB

-> BRBBBB

-> BRBRBB

-> BRBRBR

 

 

<C++소스코드>

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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
 
    int n;
    cin >> n;
    string s; cin >> s;
    char prev = s[0];
    for (int i = 1; i < n; i++) {
        if (prev == s[i]) s[i] = ' ';
        else {
            prev = s[i];
        }
    }
    int B = 0, R = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'B')B++;
        else if (s[i] == 'R') R++;
    }
    cout << 1 + min(B, R);
 
    return 0;
}
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 17521번] Byte Coin  (0) 2023.04.24
[백준 1439번] 뒤집기  (0) 2023.04.23
[백준 20115번] 에너지 드링크  (0) 2023.04.22
[백준 1343번] 폴리오미노  (0) 2023.04.22
[백준 15489번] 파스칼 삼각형  (0) 2023.04.21
반응형

문제 링크: https://www.acmicpc.net/problem/20115

 

20115번: 에너지 드링크

페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한

www.acmicpc.net

<문제 풀이> 그리디 알고리즘

 

매 순간 두 음료를 선택하여, 양이 더 적은 음료를 버린다면 에너지 드링크의 양을 최대로 만들 수 있습니다.

따라서, 우선 음료를 오름차순으로 정렬한 뒤에 가장 양이 많은 음료에 나머지 음료를 순차적으로 버리면 됩니다.

 

<C++소스코드>

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
 
int n;
double ans;
double drink[100000];
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> drink[i];
    }
 
    sort(drink, drink + n);
 
    ans = drink[n - 1];
    for (int i = 0; i < n - 1; i++) {
        ans += drink[i] / 2;
    }
    cout << ans;
 
    return 0;
}
 cs
 

 

 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1439번] 뒤집기  (0) 2023.04.23
[백준 20365번] 블로그2  (0) 2023.04.23
[백준 1343번] 폴리오미노  (0) 2023.04.22
[백준 15489번] 파스칼 삼각형  (0) 2023.04.21
[백준 16953번] A -> B  (0) 2023.04.21
반응형

문제 링크: https://www.acmicpc.net/problem/1343

 

1343번: 폴리오미노

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

www.acmicpc.net

<문제 풀이> 그리디 알고리즘

 

"XXXX"를 찾아서 모두 AAAA로 바꿔주고 그다음 "XX"를 찾아서 모두 "BB"로 바꿔주면 됩니다.

 

 

<C++소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
using namespace std;
 
string s;
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> s;
    while (s.find("XXXX") != string::npos) {
        s.replace(s.find("XXXX"),4 ,"AAAA");
    }
    while (s.find("XX") != string::npos) {
        s.replace(s.find("XX"),2, "BB");
    }
    if (s.find("X") != string::npos) cout << -1;
    else cout << s;
 
    return 0;
}
 cs
 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 20365번] 블로그2  (0) 2023.04.23
[백준 20115번] 에너지 드링크  (0) 2023.04.22
[백준 15489번] 파스칼 삼각형  (0) 2023.04.21
[백준 16953번] A -> B  (0) 2023.04.21
[백준 11508번] 2 + 1 세일  (0) 2023.04.20
반응형

문제 링크: https://www.acmicpc.net/problem/15489

 

15489번: 파스칼 삼각형

첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R)

www.acmicpc.net

<문제 풀이> 다이나믹 프로그래밍(DP), 수학

 

 

파스칼 삼각형을 아래 그림과 같이 왼쪽으로 정렬된 형태로 생각하면 2차원 배열로 쉽게 표현할 수 있습니다.

그러면 맨 왼쪽을 모두 1로 채운 뒤 ㄱ자 모양으로 파스칼 삼각형 DP 배열을 채우면 됩니다.

 

 

 

 

<C++소스코드>

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<functional>
#include<algorithm>
using namespace std;
 
int R, C, W;
 
int dp[32][32];
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> R >> C >> W;
 
    for (int i = 1; i <= 31; i++) {
        dp[i][1] = 1;
    }
 
    for (int i = 1; i <= 29; i++) {
        for (int j = 1; j <= 29; j++) {
            dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < W; i++) {
        for (int j = 0; j <= i; j++) {
            ans += dp[R + i][C + j];
        }
    }
 
    cout << ans;
 
    return 0;
}
cs
반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 20115번] 에너지 드링크  (0) 2023.04.22
[백준 1343번] 폴리오미노  (0) 2023.04.22
[백준 16953번] A -> B  (0) 2023.04.21
[백준 11508번] 2 + 1 세일  (0) 2023.04.20
[백준 1890번] 점프  (0) 2023.04.19
반응형

문제 링크: https://www.acmicpc.net/problem/16953

 

16953번: A → B

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

www.acmicpc.net

<문제 풀이>  BFS 알고리즘

 

큐에 다음 두 가지를 삽입하는 BFS를 구현하면 되는 문제입니다.

1. cur * 2 

2. cur * 10 + 1 

 

큐가 비워지기 전에 A == B가 되는 수를 찾으면 성공이고 큐가 비워졌을 때 A == B가 되는 수를 못 찾으면 실패입니다.

 

숫자 맨 뒤에 1을 추가하는 것은 2로 나누어 떨어지지 않기 때문에 숫자에 2를 곱한 것과 중복되지 않습니다.

따라서 방문 체크 배열을 만들 필요가 없습니다.

 

숫자는 최대 10^9이므로 2번 연산에서 10^9 * 10 + 1을 하면 int의 최대 크기를 넘어가기 때문에 long long 자료형을 사용해야 합니다.

 

 

<C++소스코드>

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
#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>
#include<utility>
using namespace std;
 
#define X first
#define Y second
typedef long long ll;
 
ll A, B;
void bfs() {
    queue<pair<ll, ll> >Q;
    Q.push({A * 2, 1}); //2를 곱한다.
    Q.push({A * 10 + 1, 1}); // 1을 수의 가장 오른쪽에 추가한다.
    long long cnt = 0;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (cur.X == B) {
            cout << cur.Y + 1;
            return;
        }
        if (cur.X * 2 <= B) {
            Q.push({ cur.X * 2, cur.Y + 1 }); //2를 곱한다.
        }
        if (cur.X * 10 + 1 <= B) {
            Q.push({ cur.X * 10 + 1 , cur.Y + 1}); // 1을 수의 가장 오른쪽에 추가한다.
        }
    }
    cout << "-1";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> A >> B;
 
    bfs();
    
 
    return 0;
}
 cs
 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1343번] 폴리오미노  (0) 2023.04.22
[백준 15489번] 파스칼 삼각형  (0) 2023.04.21
[백준 11508번] 2 + 1 세일  (0) 2023.04.20
[백준 1890번] 점프  (0) 2023.04.19
[백준 1758번] 알바생 강호  (0) 2023.04.19
반응형

문제 링크: https://www.acmicpc.net/problem/11508

 

11508번: 2+1 세일

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두

www.acmicpc.net

<문제 풀이> 그리디 알고리즘

 

최대한 비싼 가격을 무료로 지불해야 하므로 내림차순으로 정렬해서 인덱스를 3으로 나누었을 때 나머지가 2인 가격을 무시하면 됩니다.

 

<C++소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
 
int n;
int c[100000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(c, c + n, greater<int>());
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (i % 3 == 2) continue;
        ans += c[i];
    }
    cout << ans;
    return 0;
}
 cs
 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 15489번] 파스칼 삼각형  (0) 2023.04.21
[백준 16953번] A -> B  (0) 2023.04.21
[백준 1890번] 점프  (0) 2023.04.19
[백준 1758번] 알바생 강호  (0) 2023.04.19
[백준 13305번] 주유소  (0) 2023.04.19

+ Recent posts

티스토리툴바