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

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

 

19년도 부산 코딩경시대회에 3번으로 나왔던 문제이다.

그때도 이렇게 풀었었는데 복습할겸 풀어보았다.

 

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
#include <iostream>
#include <cmath>
#include <algorithm>
#define MOD 1000000000
using namespace std;
 
int N;
int dp[1000001][20];
 
int ans(int num, int p) {
    if (num == 0) {
        return 1;
    }
    if (num < 0 || p < 0) return 0;
    if (dp[num][p]) return dp[num][p];
 
    // 현재 값에 대해 2^p 만큼 쓰거나 안쓰고 1로만 쓰거나 둘중하나
    dp[num][p] = ans(num - pow(2, p), p)%MOD + ans(num, p-1)%MOD;
    return dp[num][p];
}
 
int main() {
    cin >> N;
 
    cout << ans(N, 19) % MOD;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

복습 20.02.08

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

BOJ 1697번 숨바꼭질  (0) 2020.01.22
BOJ 10819번 차이를 최대로  (0) 2020.01.22
BOJ 1451번 직사각형으로 나누기  (0) 2020.01.21
BOJ 1107번 리모컨  (0) 2020.01.21
BOJ 1476번 날짜 계산  (0) 2020.01.17

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

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

 

직사각형을 3군데로 나눌 수 있는 방법은 다음과 같다.

 

위의 6개 케이스가 나오게 되는데

이 경우를 반복문을 통해 합을 구해서 최댓값을 찾으면 된다.

 

임의의 fst 범위에 대한 값을 빠르게 구해와야 시간초과가 발생하지 않는다.

dp[i][k] = i행 k열 구간의 모든 수의 합이라고 가정할 때

dp[i][k] = dp[i-1][k] + dp[i][k-1] - dp[i-1][k-1] + this[i][k] 의 점화식으로 미리 계산해놓을 수 있으니

f s t 의 반복문 값만 잘 지정해주면 문제 없을 듯 하다.

 

더보기
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 <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
 
int arr[101][101];
long long dp[101][101];
 
int main() {
    int N, M;
    scanf("%d%d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int k = 1; k <= M; k++) {
            scanf("%1d", &arr[i][k]);
        }
    }
 
    for (int i = 1; i <= N; i++)
        for (int k = 1; k <= M; k++)
            dp[i][k] = dp[i - 1][k] + dp[i][k - 1] - dp[i - 1][k - 1] + arr[i][k];
 
    long long ans = 0;
    long long f, s, t;
    
    // case:1
    for (int i = 1; i <= M - 2; i++) {
        f = dp[N][i];
        for (int k = i + 1; k <= M - 1; k++) {
            s = dp[N][k] - f;
            t = dp[N][M] - s - f;
            ans = max(ans, f * s * t);
        }
    }
 
    // case:2
    for (int i = 1; i <= N - 2; i++) {
        f = dp[i][M];
        for (int k = i + 1; k <= N - 1; k++) {
            s = dp[k][M] - f;
            t = dp[N][M] - s - f;
            ans = max(ans, f * s * t);
        }
    }
 
    // case:3
    for (int i = 1; i <= M - 1; i++) {
        f = dp[N][i];
        for (int k = 1; k <= N - 1; k++) {
            s = dp[k][M] - dp[k][i];
            t = dp[N][M] - f - s;
            ans = max(ans, f * s * t);
        }
    }
 
    // case:4
    for (int i = 1; i <= M - 1; i++) {
        for (int k = 1; k <= N - 1; k++) {
            f = dp[k][i];
            s = dp[N][i] - f;
            t = dp[N][M] - f - s;
            ans = max(ans, f * s * t);
        }
    }
 
    // case:5
    for (int i = 1; i <= N - 1; i++) {
        f = dp[i][M];
        for (int k = 1; k <= M - 1; k++) {
            s = dp[N][k] - dp[i][k];
            t = dp[N][M] - f - s;
            ans = max(ans, f * s * t);
        }
    }
 
    // case:6
    for (int i = 1; i <= N - 1; i++) {
        for (int k = 1; k <= M - 1; k++) {
            f = dp[i][k];
            s = dp[i][M] - f;
            t = dp[N][M] - f - s;
            ans = max(ans, f * s * t);
        }
    }
 
    printf("%lld", ans);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 10819번 차이를 최대로  (0) 2020.01.22
BOJ 2410번 2의 멱수의 합  (0) 2020.01.22
BOJ 1107번 리모컨  (0) 2020.01.21
BOJ 1476번 날짜 계산  (0) 2020.01.17
BOJ 1744번 수 묶기  (0) 2020.01.17

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

+ Recent posts

티스토리툴바