uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1410

 

10진수 -> 2진수로 변경 후

carry 값을 0으로 만들어주면 끝나는 매우 쉬운 문제

 

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 <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    long long n1, n2;
    int a[40], b[40];
    while (1) {
        cin >> n1 >> n2;
        if (cin.eof()) break;
 
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
 
        // 10진수 -> 2진수
        string astr = "", bstr = "";
        while (n1) {
            if (n1 == 1) {
                astr += '1';
                break;
            }
            astr += (n1 % 2) + '0';
            n1 /= 2;
        }
        while (n2) {
            if (n2 == 1) {
                bstr += '1';
                break;
            }
            bstr += (n2 % 2) + '0';
            n2 /= 2;
        }
        for (int i = astr.size() - 1; i >= 0; i--) a[i] = astr[i] == '1' ? 1 : 0;
        for (int i = bstr.size() - 1; i >= 0; i--) b[i] = bstr[i] == '1' ? 1 : 0;
 
        int len = max(astr.size(), bstr.size());
        long long ans = 0;
        for (int i = 0; i < len; i++) {
            if (a[i] && b[i]) continue;
            if (a[i] || b[i]) ans += pow(2, i);
        }
        cout << ans << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

uva 384번 Slurpys, BOJ 14906번 스러피  (0) 2020.03.31
uva 10150번 Doublets  (0) 2020.03.27
uva 10010번 Where's Waldorf?  (0) 2020.03.23
uva 679 - Dropping Balls  (0) 2020.03.19
uva 10137 - the trip, BOJ 4411번  (0) 2020.03.19

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=951

 

간단한 dfs 문제

 

* 같은 방향으로 원하는 문자열을 찾으면 되는 문제이다

* 반드시 문자열을 찾을 수 있다.

* 답이 여러개인 경우 가장 왼쪽부근에 위치한 답을 출력하라고 하는데,

  그냥 행->열 순서로 탐색하면 해결된다.

 

alpha 함수는 대소문자가 같은 경우를 리턴하는 함수

 

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 <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
string arr[51];
bool visit[52][52];
int row, col;
int mx[8] = { 0,1,1,1,0,-1,-1,-1 };
int my[8] = { -1,-1,0,1,1,1,0,-1 };
 
bool alpha(char now_al, char stand) {
    if (now_al == stand || now_al - '0' + 32 == stand - '0' || now_al - '0' - 32 == stand - '0') return true;
    else return false;
}
 
bool dfs(int y, int x, int cnt, string str, int direct) {
    if (cnt == str.size()) return true;
 
    for (int i = 0; i < 8; i++) {
        if (direct == -1 || direct == i) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && yy < row && xx >= 0 && xx < col && !visit[yy][xx]) {
                if (alpha(arr[yy][xx], str[cnt])) {
                    visit[yy][xx] = true;
                    if (dfs(yy, xx, cnt + 1, str, i)) return true;
                    visit[yy][xx] = false;
                }
            }
        }
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int testcase;
   cin >> testcase;
 
    while (testcase--) {
       cin >> row >> col;
        for (int i = 0; i < row; i++)
           cin >> arr[i];
        
        vector<pair<int, pair<int, int> > > v;
        int test;
       cin >> test;
        while (test--) {
            string str;
           cin >> str;
            
            bool check = false;
 
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (alpha(str[0], arr[i][j])) {
                        if (dfs(i, j, 1, str, -1)) {
                           cout << i + 1 << " " << j + 1 << "\n";
                            memset(visit, 0, sizeof(visit));
                            check = true;
                            break;
                        }
                    }
                }
                if (check) break;
            }
        }
       cout << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

uva 10150번 Doublets  (0) 2020.03.27
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 679 - Dropping Balls  (0) 2020.03.19
uva 10137 - the trip, BOJ 4411번  (0) 2020.03.19
uva 100 - 3n+1 problem  (0) 2020.03.18

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=620

 

FBT 는 배열로 쉽게 표현가능합니다.

 

현재 위치를 flag 로 표현할 때, 

좌 -> 우 로 자식노드를 확인해주면서 마지막 리프노드에 도달하는 순서를 확인하는 문제입니다.

좌 가 false 이면 방문 true 이면 우 를 확인

우 가 false 이면 방문 true 이면 둘다 false 갱신 후 좌 부터 진입

 

재귀를 이용했습니다.

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
 
int deep;
int visit[1 << 20];
 
void dfs(int node, int now_cnt, int cnt) {
    if (node >= (1 << (deep - 1)) && now_cnt == cnt) {
        cout << node << "\n";
        return;
    }
 
    if (node >= (1 << (deep - 1))) {
        visit[node] = 1;
        return;
    }
 
    visit[node] = 1;
 
    if (!visit[node * 2]) dfs(node * 2, now_cnt, cnt);
    else if (!visit[node * 2 + 1]) dfs(node * 2 + 1, now_cnt, cnt);
    else {
        visit[node * 2] = visit[node * 2 + 1] = 0;
        dfs(node * 2, now_cnt, cnt);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--) {
        int cnt;
        cin >> deep >> cnt;
 
        for (int i = 1; i <= cnt; i++)
            dfs(1, i, cnt);
 
        memset(visit, 0, sizeof(visit));
    }
    int num = -1;
    cin >> num;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

uva 10150번 Doublets  (0) 2020.03.27
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 10010번 Where's Waldorf?  (0) 2020.03.23
uva 10137 - the trip, BOJ 4411번  (0) 2020.03.19
uva 100 - 3n+1 problem  (0) 2020.03.18

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1078

 

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

 

실수를 표현하는 방법 1)과 값을 최소화하기 위한 방식 2)을 알면 해결할 수 있는 문제입니다.

 

기본적으로 실수를 정수로 바꿔주는 캐스팅 과정에서

원하는대로 정확히 변경되지 않습니다.

 

double num 에 1.01을 입력받는 경우 디버깅으로 확인해보면 1.009999... 라는 값을 가지게 됩니다.

실수를 정수로 변환하는 과정에서 가장 간단한 방법은 0.5를 이용하는 것입니다.

 

이 문제는 계속 실수만 가지고 계산하다가는 정확한 값을 얻을 수 없을 것 같아서 아예 정수로 바꿔놓고 계산했습니다.

2번째 자리까지에 대한 값만 알면 되므로 정수 = 실수*100+0.5 로 캐스팅하여 이용했습니다.

 

풀이과정은 다음과 같습니다.

 

총 금액에 대한 평균을 구할 수 있고, 모든 사람은 최소한 평균이상의 금액은 지불해야 합니다.

이 때 총 금액을 인원수에 맞게 나누었을 때 나머지**)는

"정확히 나눌 수 없으니 서로 1센트 정도는 더 내서 채워야되는 금액" 을 의미합니다.

 

그럼 필요한 정보들은 다음과 같아집니다.

1) 현재 사람들이 낸 금액

2) 현재 사람들이 내야할 금액

 

2) 현재 사람들이 내야할 금액은 기본적으로 총금액에 대한 평균값은 모두 가져야 할 것이고,

나머지**) 를 이용해서 2)의 값을 다시 계산해주면 됩니다.

 

결국 정답은 1) - 2) 또는 2) - 1) 에 대한 값이 되는데

중요한 것은 내야할 금액을 최소화 (돈을 많이 낸 사람이 돈을 최대한 돌려받는 경우) 하는 것입니다.

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int total;
    int person;
    double p;
    vector<int> pay, real_pay;
    cin >> person;
    while (person) {
        total = 0;
        for (int i = 0; i < person; i++) {
            cin >> p;
            pay.push_back(p * 100 + 0.5);
            total += pay[i];
        }
 
        int indivi = total / person;
        int mod = total % person;
        total = 0;
 
        sort(pay.begin(), pay.end(), greater<int>());
        for (int i = 0; i < person; i++) real_pay.push_back(indivi);
        for (int i = 0; i < mod; i++) real_pay[i]++;
        for (int i = 0; i < person; i++) total += abs(real_pay[i] - pay[i]);
        cout << fixed;
        cout.precision(2);
        cout << "$" << (total / 2) / 100.0 << "\n";
        cin >> person;
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

uva 10150번 Doublets  (0) 2020.03.27
uva 10469번 To Carry or not to Carry  (0) 2020.03.23
uva 10010번 Where's Waldorf?  (0) 2020.03.23
uva 679 - Dropping Balls  (0) 2020.03.19
uva 100 - 3n+1 problem  (0) 2020.03.18

+ Recent posts

티스토리툴바