BOJ : https://www.acmicpc.net/problem/2294

github : https://github.com/junho0956/Algorithm/blob/master/2294/2294/%EC%86%8C%EC%8A%A4.cpp

 

동전2 문제의 경우 2차원 dp로 해결할 수 있습니다.

지금까지 합쳐진 돈의 액수를 total로 보고 재귀로 구현해주시면 쉽게 해결할 수 있습니다.

 

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>
#include <algorithm>
#include <cstring>
using namespace std;
 
int dp[101][10001];
int N, won;
int arr[101];
 
int dfs(int nth, int total) {
    if (nth > N || total > won) return 1000;
    if (total == won) 
        return 0;
    
    int& res = dp[nth][total];
    if (res != -1)return res;
 
    res = 1000;
    for (int i = nth; i <= N; i++) {
        res = min(res, dfs(i, total + arr[i]) + 1);
    }
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> won;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= N; i++) cin >> arr[i];
 
    int ans = dfs(1, 0);
    if (ans == 1000) cout << "-1";
    else cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1916번 최소비용 구하기  (0) 2020.02.23
BOJ 1753번 최단경로  (0) 2020.02.23
BOJ 10835번 카드게임  (0) 2020.02.21
BOJ 10995번 별 찍기 - 20  (0) 2020.02.21
BOJ 11654번 아스키 코드  (0) 2020.02.21

BOJ : https://www.acmicpc.net/problem/10835

github : https://github.com/junho0956/Algorithm/blob/master/10835/10835/%EC%86%8C%EC%8A%A4.cpp

 

재귀를 통해 쉽게 해결할 수 있었습니다.

dp를 0이 아닌 -1같은 가능성 없는 값으로 초기화하는 작업을 들이는 습관을 가져야겠습니다.

 

조건에서 오른쪽 더미에 있는 카드가 왼쪽 더미에 있는 카드보다 작을 경우 오른쪽 더미의 카드 점수를 더하라고 했으므로 재귀에서 조건을 다음과 같이 두 가지 경우의 수로 나누어 주었습니다

 

=> 오른쪽 더미에 있는 카드가 왼쪽 더미에 있는 카드보다 작을 경우

1) 오른쪽 카드만큼 더하고 오른쪽 더미 인덱스를 늘린다

2) 왼쪽 카드 인덱스를 늘린다

3) 왼쪽, 오른쪽 카드 인덱스를 늘린다

=> 그 외

1) 왼쪽 카드 인덱스를 늘린다

2) 왼쪽, 오른쪽 카드 인덱스를 늘린다

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
#define maxi 987654321
int N;
int lpile[2001];
int rpile[2001];
int dp[2001][2001];
 
int dfs(int left, int right) {
    if (left >= N || right >= N) return 0;
 
    int& res = dp[left][right];
    if (res!=-1) return res;
 
    int ans = 0;
    if (lpile[left] > rpile[right]) ans = max(dfs(left, right + 1) + rpile[right], max(dfs(left + 1, right), dfs(left + 1, right + 1)));
    else ans = max(dfs(left + 1, right), dfs(left + 1, right + 1));
 
    return res = ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) cin >> lpile[i];
    for (int i = 0; i < N; i++) cin >> rpile[i];
 
    cout << dfs(0,0);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1753번 최단경로  (0) 2020.02.23
BOJ 2294번 동전 2  (0) 2020.02.21
BOJ 10995번 별 찍기 - 20  (0) 2020.02.21
BOJ 11654번 아스키 코드  (0) 2020.02.21
BOJ 1149번 RGB거리  (0) 2020.02.21

BOJ : https://www.acmicpc.net/problem/10995

github : https://github.com/junho0956/Algorithm/blob/master/10995/10995/%EC%86%8C%EC%8A%A4.cpp

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
 
int main() {
    int n; cin >> n;
    int t = 1;
    while (t<=n) {
        if (t % 2) {
            int cnt = n - 1;
            for (int i = 1; i <= n; i++) {
                cout << "*";
                if (cnt) cout << " ", cnt--;
            }
        }
        else {
            for (int i = 1; i <= n; i++) {
                cout << " *";
            }
        }
        t++;
        cout << "\n";
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2294번 동전 2  (0) 2020.02.21
BOJ 10835번 카드게임  (0) 2020.02.21
BOJ 11654번 아스키 코드  (0) 2020.02.21
BOJ 1149번 RGB거리  (0) 2020.02.21
BOJ 2941번 크로아티아 알파벳  (0) 2020.02.21

BOJ : https://www.acmicpc.net/problem/11654

 

아스키코드를 편하게 이용하는 방법은

char 형 문자를 %d로 출력하는 것입니다.

 

1
2
3
4
5
6
7
8
9
#include <cstdio>
#pragma warning(disable:4996)
 
int main() {
    char ch;
    scanf("%c", &ch);
    printf("%d", ch);
    return 0;
}

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10835번 카드게임  (0) 2020.02.21
BOJ 10995번 별 찍기 - 20  (0) 2020.02.21
BOJ 1149번 RGB거리  (0) 2020.02.21
BOJ 2941번 크로아티아 알파벳  (0) 2020.02.21
BOJ 15993번 1, 2, 3 더하기 8  (0) 2020.02.20

+ Recent posts

티스토리툴바