https://www.acmicpc.net/problem/15673


수열에서 연속 부분 수열 두개를 골라 그 곱이 가장 클 때 얼마나 클지 알아내야 한다.


연속 부분 수열이 얼마나 클지를 알아내는 방법은 디피 문제를 풀 때 쉽게 접할 수 있는 문제다.


dp[x]를 x번째 인자를 포함한 부분 수열 중 합이 가장 큰 수를 저장하게 정의해 놓으면,


dp[x]는 dp[x-1]이 음수인 경우와 양수인 경우로 나눠 원타임에 값이 정해진다.



또한 새로운 디피 배열 lmax를 정의할 수 있게 되는데,


이번엔 lmax[x]는 x번째 인자를 반드시 포함하지 않아도, x까지 수열의 부분 수열 중 합이 가장 큰 수를 저장한다고 정의해 놓으면,


lmax[x] = max(lmax[x-1], dp[x])로 원타임에 값이 정해진다.


즉 x가 포함되던지 안되던지 두 케이스 중 큰 값으로 정해지는 것이다.



이를 응용해서 왼쪽에서 부터, 오른쪽에서 부터, 최대합 부분수열, 최소합 부분수열을 모두 n타임에 구할 수 있다.


그러고 난 다음 부분 수열 두 개로 나눌 기준점을 n개 중에 골라서 비교하는 작업도 n타임에 수행할 수 있다.


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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int n;
ll arr[100001];
 
ll dmin[100001], dmax[100001];
ll lmin[100001], lmax[100001];
ll rmin[100001], rmax[100001];
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
 
    lmin[1= lmax[1= dmin[1= dmax[1= arr[1];
 
    for (int i = 2; i <= n; ++i) {
        if (dmax[i - 1< 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i - 1+ arr[i];
 
        if (dmin[i - 1> 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i - 1+ arr[i];
 
        lmin[i] = min(lmin[i - 1], dmin[i]);
        lmax[i] = max(lmax[i - 1], dmax[i]);
    }
 
    memset(dmin, 0sizeof(dmin));
    memset(dmax, 0sizeof(dmax));
 
    rmin[n] = rmax[n] = dmin[n] = dmax[n] = arr[n];
 
    for (int i = n - 1; i >= 1--i) {
        if (dmax[i + 1< 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i + 1+ arr[i];
 
        if (dmin[i + 1> 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i + 1+ arr[i];
 
        rmin[i] = min(rmin[i + 1], dmin[i]);
        rmax[i] = max(rmax[i + 1], dmax[i]);
    }
 
    ll ans = LLONG_MIN;
    for (int i = 1; i < n; ++i) {
        ans = max(ans, lmin[i] * rmin[i + 1]);
        ans = max(ans, lmin[i] * rmax[i + 1]);
        ans = max(ans, lmax[i] * rmin[i + 1]);
        ans = max(ans, lmax[i] * rmax[i + 1]);
    }
 
    cout << ans;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준)15673 헤븐스 키친 2  (0) 2018.10.02
백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

https://www.acmicpc.net/problem/15668


0 ~ 9 까지 숫자 카드 스티커들을 한 번씩만 사용해 n = a + b 의 a와 b를 만들어야 한다.



여러 풀이 중에 내 생각에 제일 기똥찬 풀이는,


a와 b중에 작은 수를 b라고 하면, b의 가능 범위가 작아지므로, 완탐으로 때릴 수 있다는 것이다.



b에 스티커 5장을 쓰면 a도 5장이 되므로 b엔 최대 5장까지만 쓸 수 있다.


또한 b의 맨 앞자리는 끽 해야 8이므로, 1~87654가 b의 가능범위이다.


b가 정해지면 a도 정해지므로, 구만번 만에 풀리는 문제.



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 <bits/stdc++.h>
using namespace std;
 
int n;
 
bool func(int x, int& st) {
    while (x) {
        int tmp = (1 << (x % 10));
        if (st & tmp)
            return false;
 
        st |= tmp;
        x /= 10;
    }
 
    return true;
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= 87654 && i < n; ++i) {
        int used = 0;
 
        if (!func(i, used))
            continue;
        if (!func(n - i, used))
            continue;
 
        cout << n - i << " + " << i;
        return 0;
    }
 
    cout << -1;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 15668 방 번호  (0) 2018.10.02
백준) 16116 작은 큐브러버  (0) 2018.10.01
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

https://www.acmicpc.net/problem/16116


구현이지만 논리력에 따라 // 관찰력에 따라 코드가 짧아질 수 있는 문제



다음을 관찰하면 코드가 짧아진다.



한 큐브가 [a b c] 였다면, 반드시 나머지 일곱 개 중에 윗 그림과 같은 세 개의 큐브가 존재해야 한다.


헌데 큐브는 요리 조리 돌려도 똑같기 때문에


한 큐브 마다 -> 세 가지 방향으로 -> 나머지 7가지 큐브 중에 -> 두면이 맞닿고 같은 큐브가 존재(중요) -> 그것도 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
#include <stdio.h>
 
char str[6];
char cb[8][4];
 
int main() {
    for (int i = 0; i < 8++i) {
        fgets(str, sizeof(str), stdin);
        cb[i][0= str[0];
        cb[i][1= str[2];
        cb[i][2= str[4];
        fgets(str, sizeof(str), stdin);
    }
 
    bool cannot = false;
    for (int i = 0; i < 8++i) {
        for (int j = 0; j < 3++j) {
            int left = cb[i][j];
            int top = cb[i][(j + 1) % 3];
            int cnt = 0;
 
            for (int k = 0; k < 8++k) {
                if (i != k) {
                    for (int l = 0; l < 3++l) {
                        if (cb[k][l] == left && cb[k][(l + 2) % 3== top) {
                            cnt++;
                        }
                    }
                }
            }
 
            if (cnt != 1)
                cannot = true;
        }
    }
 
    if (cannot)
        puts("NO");
    else
        puts("YES");
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 15668 방 번호  (0) 2018.10.02
백준) 16116 작은 큐브러버  (0) 2018.10.01
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

+ Recent posts