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

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

 

알아야하는 것은 리모컨 채널에 접근할 수 있는 방법이다.

1. + - 버튼만 눌러서 이동한다

2. 누를수있는 버튼으로 이동 후에, + - 으로 이동한다.

 

처음에는 어떻게 가고자하는 버튼에 최대한 가깝게 갈 수 있을까

여러가지 많이 시도해봤는데 4번 연속 틀리면서 좀 더 간단한 방법을 생각해보고자 했다.

어차피 채널은 최대 50만번이여서 완전탐색의 마구잡이식으로 다 확인해볼까 싶어서

필요한 범위내를 전부 탐색해줬더니 의외로 빠른 시간내에 문제를 해결할 수 있었다.

 

.. 알고리즘은 정말 너무어렵다 ..

 

 

더보기
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>
using namespace std;
 
 
int moveCH, broken;
bool brokenBtn[10];
 
bool possible(int ch) {
    int number;
    // 채널이 0번일수도 있다
    if (ch == 0) {
        if (brokenBtn[0]) return true;
        else return false;
    }
 
    while (ch) {
        number = ch % 10;
        ch /= 10;
        if (brokenBtn[number] == false) return false;
    }
 
    return true;
}
 
int click(int ch) {
    if (ch == 0) return 1+moveCH;
    else {
        int num = 0;
        int channel = ch;
        while (ch) num++, ch /= 10;
 
        num += abs(moveCH - channel);
 
        return num;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int i = 0; i < 10; i++) brokenBtn[i] = 1;
    cin >> moveCH >> broken;
 
    for (int i = 0; i < broken; i++) {
        int a; cin >> a;
        brokenBtn[a] = 0;
    }
 
    /*
    채널을 이동할 수 있는 방법
    1. + - 버튼만 눌러서 이동
    2. 임의의 버튼으로 이동한 후에 + - 버튼을 눌러서 이동
    */
 
    // 채널은 최대 50만번까지 있으니 채널의 자리수를 고려하여 100만까지 탐색해본다
    // 기본 값은 + - 버튼으로만 이동하는 경우
    int min_click = abs(moveCH-100);
    for (int i = 0; i <= 1000000; i++) {
        // 채널로 이동이 된다면 이동 후, + - 까지 같이 계산한다
        if (possible(i)) {
            min_click = min(min_click, click(i));
        }
    }
 
    cout << min_click;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

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

BOJ 2410번 2의 멱수의 합  (0) 2020.01.22
BOJ 1451번 직사각형으로 나누기  (0) 2020.01.21
BOJ 1476번 날짜 계산  (0) 2020.01.17
BOJ 1744번 수 묶기  (0) 2020.01.17
BOJ 11399번 ATM  (0) 2020.01.17

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

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

 

e, s, m 이 주어지면

e 를 고정시키고 s m 이 정확히 맞아 떨어질때까지 무한탐색하였습니다.

 

더보기
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
#include <iostream>
using namespace std;
 
int main() {
    int e, s, m;
    cin >> e >> s >> m;
 
    int total = 1;
    int ss = 1, mm = 1;
 
    ss += (e - 1);
    mm += (e - 1);
 
    total += (e - 1);
    while (1) {
        if (ss == s && mm == m) break;
        ss += 15, mm += 15;
        if (ss > 28) ss %= 28;
        if (mm > 19) mm %= 19;
        total += 15;
    }
 
    cout << total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1451번 직사각형으로 나누기  (0) 2020.01.21
BOJ 1107번 리모컨  (0) 2020.01.21
BOJ 1744번 수 묶기  (0) 2020.01.17
BOJ 11399번 ATM  (0) 2020.01.17
BOJ 1931번 회의실 배정  (0) 2020.01.17

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

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

 

수 묶기 문제는 일정 수열이 주어졌을 때 이 수열의 합을 최대한으로 만드는 문제입니다. 

여기서는 임의의 숫자를 다른 숫자와 묶는게 가능한데 이 묶기가 * 곱하기입니다.

 

예를 들어 0 1 2 4 3 5 라는 수가 있고 이를 모두 더하면 15가 됩니다.

하지만 (4,5) (2,3) 을 묶으면(곱하면) 0 1 (2*3) (4*5) 가 되고 이를 합하면 27이 됩니다.

 

저는 이런식으로 문제를 접근했습니다.

정수가 나올 수 있는 범위는 -10000~10000 이므로 일단 음수가 나올 수 있음에 주의해야합니다.

마찬가지로 0도 나올 수 있다는거죠!

 

그럼 양수는 최대한 높은 것끼리 곱해주는게 총 합에 이득일 것이고,

음수는 최대한 작은 것 끼리 곱해주는게 총 합에 이득일 것입니다.

 

여기서 또 뭘 생각해보았냐면

 

0과 1에 주의하는 것입니다.

1보다 큰 양수는 0과 곱해지면 무조건 손해를 보고 1과 곱해져도 무조건 손해입니다.

1 2 가 있다면 1*2 를 하는 것은 손해니까요

그리고, 음수는 분명 짝을 지어서 서로 곱하는게 무조건 이득입니다.

근데, 짝을 못찾는 음수가 남을 수 있으니, 이는 0과 곱해서 그냥 0으로 만들어버리는 것입니다.

이 경우는 단 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
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<pair<int,int> > v;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N, num;
    int zero = 0;
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> num;
        v.push_back({ num, 1 });
    }
 
    sort(v.begin(), v.end());
 
    int fin_idx = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].first >= 0) {
            fin_idx = i;
            break;
        }
        if (i + 1 <= v.size() - 1 && v[i+1].first <= 0) {
            v[i].first *= v[i + 1].first;
            v[i + 1].second = -1;
            i++;
        }
    }
 
    for (int i = v.size() - 1; i >= fin_idx; i--) {
        if (v[i].first <= 1) break;
        if (i - 1 >= fin_idx && v[i - 1].first > 1) {
            v[i].first *= v[i - 1].first;
            v[i - 1].second = -1;
            i--;
        }
    }
 
    int total = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i].second != -1) total += v[i].first;
    }
 
    cout << total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1107번 리모컨  (0) 2020.01.21
BOJ 1476번 날짜 계산  (0) 2020.01.17
BOJ 11399번 ATM  (0) 2020.01.17
BOJ 1931번 회의실 배정  (0) 2020.01.17
BOJ 1783번 병든 나이트  (0) 2020.01.17

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

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

 

현재 사람이 앞사람이 돈을 인출하는데 걸리는시간을 최소화하기 위해서는 앞사람이 인출하는 시간을 줄이면 된다.

==> ATM 인출 시간을 가장 작게 줄이는 방법은 정렬을 해주는 것으로 해결할 수 있다.

 

더보기
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 <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int N, a;
vector<int> v;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    int total = 0;
    for (int i = 0; i < v.size(); i++) {
        for (int k = 0; k <= i; k++) {
            total += v[k];
        }
    }
 
    cout << total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1476번 날짜 계산  (0) 2020.01.17
BOJ 1744번 수 묶기  (0) 2020.01.17
BOJ 1931번 회의실 배정  (0) 2020.01.17
BOJ 1783번 병든 나이트  (0) 2020.01.17
BOJ 10610번 30  (0) 2020.01.17

+ Recent posts

티스토리툴바