오늘 뭐했지

https://boj.ma/5546/t 

N일동안 파스타를 먹을건데, 파스타의 종류는 3가지이고 3일 연속으로 같은 종류의 파스타를 먹으면 안됩니다.

그리고 특정 날짜에 반드시 먹어야 하는 파스타의 종류가 주어집니다.

N일까지 파스타를 먹는 모든 경우의 수를 구하는 문제입니다.

완전탐색부터 접근해봅니다.

재귀함수로 완전탐색을 할건데,

recur(cur, a, b) := 현재 cur일이고, 어제 a종류의 파스타, 그제 b종류의 파스타를 먹었을때 N일까지 도착하는 경우의 수

라고 정의 하고 완전탐색을 하면

제가 계산한건 대략 9^100 이라고 생각했는데 혹시 아니라면 댓글 부탁드립니다.

9^100번 연산을 하면 시간초과라는 것을 알 수 있습니다.

현재 5일차고, 어제 1번종류, 그제 2번 종류 파스타를 먹었다고 해봅시다. 그리고 우리는 10일차까지 가야합니다.

그럼 1 ~ 4일차 까지 1 2 2 1, 3 2 2 1, 2 1 2 1, ... 등과 같이 채울 수 있을텐데, 1 ~ 4일차에 어떤 선택을 했든 상관없이

"현재 5일차고, 어제 1번종류, 그제 2번 종류 파스타를 먹었다" 에서 N일차까지 가는 경우의 수는 항상 일정할 것입니다.

다음 경우에 영향을 주는 요소는 어제랑 그제 뿐이니까요.

따라서 dp를 적용할 수 있습니다.

완전탐색에서의 함수 정의를 그대로 사용하면 됩니다.

code(c++)

#include <bits/stdc++.h>
#define endl "\n"
#define NM 101010
#define MAX 1010100
#define BIAS 1048576
#define MOD 20170805
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, k;
int arr[111], dp[111][111][111];
const int mod = 10000;

int recur(int cur, int a, int b){ // 현재 cur일이고, 어제 a, 그제 b 먹음
    if (cur == n + 1) return 1;
    int&ret = dp[cur][a][b];
    if(~ret) return ret;
    ret = 0;
    if (arr[cur]){ // 오늘 먹어야할게 정해져있음
        if (a == b && b == arr[cur]) return 0;
        ret += recur(cur + 1, arr[cur], a);
        ret %= mod;
    }
    else{
        for (int i = 1; i <= 3; i++){
            if (a == b && b == i) continue;
            ret += recur(cur + 1, i, a);
            ret %= mod;
        }
    }
    return ret;
}

void input() {
    cin >> n >> k;
    for (int i = 0; i < k ; i++){
        int a, b;
        cin >> a >> b;
        arr[a] = b;
    }
}

void pro() {
    memset(dp, -1, sizeof dp);
    cout << recur(1, 0, 0) << endl;
}

int main() {
    fastio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    input();
    pro();
    return 0;
}

https://boj.ma/1756/t 

깊이 별 오븐의 지름과 오븐에 넣으려고 하는 피자 반죽의 지름들이 주어집니다.

반죽을 모두 오븐에 넣으려고 할때 가장 높이 위치하는 반죽의 높이를 출력하는 문제입니다.

완전탐색부터 접근해봅니다.

반죽은 만든 순서대로 넣기때문에 반죽의 지름이 저장된 배열을 앞에서부터 모두 확인하며

오븐의 지름이 저장된 배열에서 처음으로 반죽의 지름보다 작아지는 위치의 바로 앞에 반죽을 넣으면 됩니다.

하지만 오븐의 지름이 주어지는 배열의 크기가 최대 30만, 반죽의 개수도 최대 30만이기 때문에

최악의 경우

입력이

300000 300000

300000 299999 299998 ... 1

1 2 3 ... 300000

형태로 주어진다면

O(300000 * 300000)이기 때문에 시간초과가 발생합니다.

모든 오븐의 배열을 확인하며 처음으로 나보다 작아지는 위치가 궁금하고 이것을 완전탐색으로 확인하는 것이 오래걸리니

이것을 최적화할 방법을 생각해봅시다.

오븐 배열의 앞에서부터 순회하며 처음으로 나보다 작아지는 위치가 궁금한것이니 나보다 크거나 같은것들에 대해는 신경쓰지 않아도 됩니다.

따라서 어떤 인덱스 i에 대해 0 ~ i위치까지의 최소값만 알면 됩니다. 그럼 반죽이 i위치까지 들어갈 수 있는지 알 수 있습니다.

이것을 저장한 배열을 prefix_min 이라고 하겠습니다.

prefix_min[i] := 오븐배열의 0 ~ i번 값까지의 최소값

이 배열에서 반죽이 들어갈 수 있는 위치중에 가장 깊은 위치에 넣으면 됩니다.

prefix_min 배열의 형태가

5 5 5 4 4 2 2 2 1 1 1

이라고 생각해봅시다.

반죽 지름이 3짜리인 반죽이 위 배열에서 값이 2가 되는 위치 이후로는 절대 답이 될 수 없습니다.

여기서 이분탐색을 떠올려 구현했습니다.

최종적으로 누적합 + 이분탐색을 통해 해결했습니다.

import sys
input = sys.stdin.readline

d, n = map(int, input().split())
oven = list(map(int, input().split()))
pizza = list(map(int, input().split()))
prefix_min = [0] * d
prefix_min[0] = oven[0]
for i in range(1, d):
    prefix_min[i] = min(prefix_min[i - 1], oven[i])
ans = -1
s, e = 0, d - 1
for i in pizza:
    # 반죽이 들어갈 수 있는 위치중 가장 깊은곳 찾기
    s = 0
    tmp = -1
    while s <= e:
        mid = s + e >> 1
        if prefix_min[mid] >= i:
            tmp = mid
            s = mid + 1
        else:
            e = mid - 1
    if ~tmp: # tmp가 -1이 아니라면 == 들어갈 위치를 찾았다
        ans = tmp
        e = tmp - 1
    else: # 못들어감
        print(0)
        exit()
print(ans + 1)

prefix_min 배열만 만들어 놓고 이 배열의 뒤에서부터 순회하며 답을 찾아나가는 방식도 가능합니다.

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

A도시와 B도시를 잇는 모든 최단경로상의 정점을 구하는 문제입니다.

가중치가 있는 그래프에서 최단경로를 찾아야 하는 문제이기 때문에 다익스트라를 써야겠다는건 알 것 같습니다.

처음 문제를 읽고 최단경로상의 정점을 구해야한다는 것만 읽고 역추적을 해야 하나 고민했습니다.

하지만 가능한 최단경로가 여러가지가 될 수 있고 그 모든 것이 정답이 될 수 있습니다.

단순하게 완전탐색부터 생각하면

A -> B 까지의 최단거리를 X라 하고, 모든 정점(i)에 대해 다익스트라를 돌리며 dist[A] + dist[B] == X이면 i번 정점을 정답에 추가하면 됩니다.

하지만 이렇게 하면 시간복잡도가 O(N^2logM)이 되어 시간초과입니다.

어떤 정점 i에서 A까지의 최단거리와 B까지의 최단거리의 합이 A부터 B까지의 최단거리가 되어야 하는 i들이 궁금한건데,

이것은 정점 A에서 i까지의 최단거리와 B에서 i까지의 최단거리의 합과 동일합니다.

따라서 A에서 다익스트라를 돌려서 나온 거리 배열을 dist_a라 하고,

B에서 다익스트라를 돌려 나온 거리 배열을 dist_b라고 했을때,

모든 1 ~ N번 정점에 대해

dist_a[i] + dist_b[i] == dist_a[B] 인 i들이 정답일 것입니다.

다익스트라 두 번후에 모든 정점에대해 확인하는 것만 하면 되니 시간복잡도가 O(NlogM)으로 줄어 시간 내에 통과 가능합니다.

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

케이크를 자를건데 자를 수 있는 M가지 지점이 있고 Q번 잘랐을때 가장 작은 조각의 길이를 최대화 하는 문제입니다.

완전탐색부터 접근을 해봅시다.

가장 떠올리기 쉬운 완전탐색 접근은 "가장 작은 조각이 Xcm이상일때 자르는 것이 가능한가"에 대해 모든 2 ~ L까지 해보는 것입니다.

모든 2 ~ L에 대해 확인하며 잘라본다면 특정 시점부터 불가능한 지점이 나올것이고, 직전 지점이 정답일 것입니다.

완전탐색을 위 방법 그대로 시도한다면 시간초과입니다.

위와 같은 완전탐색 접근을 하면서 특정 시점부터 불가능한 지점  이라는 관찰을 통해 정답이 단조성을 띈다는 것을 알 수 있습니다.

정답이 단조성을 띄기 때문에 이분탐색을 통한 최적화가 가능합니다.

code(c++)

#include <bits/stdc++.h>

#define endl "\n"
#define NM 303030
#define MAX 101010
#define BIAS 1048576
#define MOD 20170805
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m, l;
int arr[1111];

tuple<int, int> ok(int x){
    int cnt = 0;
    int prev = 0;
    for (int k = 0 ; k <= m; k++){
        if (arr[k] - prev >= x){
            cnt++;
            prev = arr[k];
        }
    }
    return {cnt, x};
}

void input() {
    cin >> n >> m >> l;
    for (int i = 0; i < m; i++) cin >> arr[i];
    arr[m] = l;
}

void pro() {
    for (int i = 0 ; i < n ; i++){
        int x;
        cin >> x;
        int s = 0;
        int e = arr[m - 1];
        int ans = 0;
        while (s <= e){
            int mid = s + e >> 1;
            auto [cnt, tmp] = ok(mid);
            if (cnt > x){
                s = mid + 1;
                ans = max(ans, tmp);
            }else{
                e = mid - 1;
            }
        }
        cout << ans << endl;
    }
}

int main() {
    fastio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    input();
    pro();
    return 0;
}