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

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

 

재귀로 dp문제를 푸는 실력이 정말 조금씩이라도 늘고있다는 느낌을 받아서 기분 좋습니다..ㅠㅠ

 

cash 를 현재 가진 돈이라고 가정했을 때 dp[cash] 를 이용해서 

현재 가진 돈으로 구매할 수 있는 사탕에 대한 모든 경우를 확인했습니다.

소수점은 정확히 계산하기 위해 double 로 받은 후 *100을 해서 int형으로 계산하였습니다.

 

** 테스트케이스가 추가되었네요 **

 

아마 *100 으로도 통과하는 소스가 있다는 글이 아니였을까 생각합니다.

*100을 곱할 때 반올림을 고려해서 0.5를 더해주면 통과할 수 있습니다

형식은(int)(double*100+0.5) 입니다

 

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
long long dp[10001];
pair<int, int> arr[5001];
long long ans;
int n;
 
long long solve(int cash) {
    long long& res = dp[cash];
    if (res) return res;
 
    long long val = 0;
    for (int i = 0; i < n; i++) {
        if (cash - arr[i].second >= 0)
            val = max(val, solve(cash - arr[i].second) + arr[i].first);
    }
 
    return res = val;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    while (1) {
        double m;
        memset(dp, 0, sizeof(dp));
        cin >> n >> m;
        if (!n && !m) break;
 
        int cash = m * 100;
        for (int i = 0; i < n; i++) {
            int a;
            double b;
            cin >> a >> b;
            arr[i].first = a, arr[i].second = b * 100;
        }
 
        cout << solve(cash) << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2605번 줄 세우기  (0) 2020.02.10
BOJ 1681번 줄 세우기  (0) 2020.02.10
BOJ 9507번 Generations of Tribbles  (0) 2020.02.10
BOJ 1914번 하노이 탑  (0) 2020.02.10
BOJ 11722번 가장 긴 감소하는 부분수열  (0) 2020.02.09

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

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

 

문제에서 0 1 2 3 4 에 대한 dp 값이 주어져있기 때문에 조건문이 없어도

문제를 해결할 수 있습니다.

 

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
#include <iostream>
using namespace std;
typedef long long ll;
ll dp[68] = { 1,1,2,4,8, };
 
ll solve(int num) {
    
    ll& res = dp[num];
    if (res) return res;
 
    return res = solve(num - 1) + solve(num - 2) + solve(num - 3) + solve(num - 4);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    solve(67);
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dp[n] << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1681번 줄 세우기  (0) 2020.02.10
BOJ 4781번 사탕가게  (0) 2020.02.10
BOJ 1914번 하노이 탑  (0) 2020.02.10
BOJ 11722번 가장 긴 감소하는 부분수열  (0) 2020.02.09
BOJ 1003번 피보나치 함수  (0) 2020.02.09

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

github : https://github.com/junho0956/Algorithm/tree/master/1914

 

N 이 클경우 long long 으로도 표현못한다는 것을 알고 스트링으로 구현하였습니다.

구현하고 나니 to_string 이라는 좋은 함수가 있다는걸 알게되었습니다...............

 

하노이의 경우는 https://junho0956.tistory.com/33에서 설명하였습니다.

 

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
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
 
long long dp[22];
int N;
 
void hanoi(int cnt, int to, int from, int no) {
    
    if (cnt == 1) {
        cout << to << " " << from << "\n";
        return;
    }
 
    hanoi(cnt - 1, to, no, from);
    hanoi(1, to, from, no);
    hanoi(cnt - 1, no, from, to);
}
 
void solve(int len, string str) {
 
    if (len == N) {
        int carry = 0;
        int idx = str.length() - 2;
        if (str[str.length() - 1] == '0') {
            str[str.length() - 1] = '9';
            carry = 1;
        }
        else str[idx + 1] = ((str[idx + 1] - '0') - 1) + '0';
        while (carry) {
            if (str[idx] == '0') str[idx--] = '9';
            else {
                str[idx] = ((str[idx] - '0') - 1) + '0';
                carry = 0;
            }
        }
 
        for (int i = 0; i < str.length(); i++) cout << str[i];
        cout << "\n";
        return;
    }
 
    string str2;
    int carry = 0;
    for (int i = str.length() - 1; i >= 0; i--) {
        int num = str[i] - '0';
        int makenum = num * 2 + carry;
        if (makenum > 9) carry = 1, makenum %= 10;
        else carry = 0;
        str2 += makenum + '0';
    }
 
    if (carry) str2 += 1 + '0';
    reverse(str2.begin(), str2.end());
 
    solve(len + 1, str2);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> N;
    dp[1] = 1, dp[2] = 3, dp[3] = 7;
    for (int i = 4; i <= 20; i++) dp[i] = pow(2, i) - 1;
 
    if (N <= 20) {
        cout << dp[N] << "\n";
        hanoi(N, 1, 3, 2);
    }
    else {
        int cnt = 0;
        string str;
        long long num = dp[20] + 1, num2 = dp[20] + 1;
        while (num) {
            num /= 10, cnt++;
        }
        int val = pow(10, cnt-1);
        while (num2) {
            str += (num2 / val) + '0', num2 %= val, val /= 10;
        }
 
        solve(20, str);
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 4781번 사탕가게  (0) 2020.02.10
BOJ 9507번 Generations of Tribbles  (0) 2020.02.10
BOJ 11722번 가장 긴 감소하는 부분수열  (0) 2020.02.09
BOJ 1003번 피보나치 함수  (0) 2020.02.09
BOJ 2193번 이친수  (0) 2020.02.09

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

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

 

 

가장 긴 감소하는 부분수열을 이룰려면

현재 키값에 대해

1) 같으면 반환

2) 현재 위치가 키값보다 크면 오른쪽탐색

3) 현재 위치가 키값보다 작으면 왼쪽탐색

위 3가지 방법으로 문제를 해결하면 됩니다.

 

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 <math.h>
#include <algorithm>
using namespace std;
 
int dp[1000];
int arr[1000];
 
int bound(int s, int e, int key) {
    int mid;
    while (s < e) {
        mid = (s + e) / 2;
        // 감소하는 수열
        // 현재키값보다 작으면 덮는다
        // 현재키값보다 크면 못덮는다
        // 현재키값과 같으면 정지
        // => 현재키값보다 작거나 같은 위치를 찾는다
        if (dp[mid] == key) return mid;
        else if (dp[mid] < key) e = mid;
        else if (dp[mid] > key) s = mid + 1;
    }
 
    return e;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp[0] = arr[0];
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (arr[i] < dp[lis]) {
            dp[++lis] = arr[i];
        }
        else {
            // 감소하는 수열
            int lower = bound(0, lis, arr[i]);
            dp[lower] = arr[i];
        }
    }
 
    cout << lis+1;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

 

복습 20.02.09

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

BOJ 9507번 Generations of Tribbles  (0) 2020.02.10
BOJ 1914번 하노이 탑  (0) 2020.02.10
BOJ 1003번 피보나치 함수  (0) 2020.02.09
BOJ 2193번 이친수  (0) 2020.02.09
BOJ 2302번 극장 좌석  (0) 2020.02.09

+ Recent posts

티스토리툴바