CLASS 7 - P4

2673번: 교차하지 않는 원의 현들의 최대집합 - DP

//원의 현들의 교차만 중요하므로, 1부터 100까지의 좌표를 수평선상에 놓고 생각할 수 있다.
//ex) 현 (1, 45) -> 구간 [1, 45], 현 (11, 65) -> 구간 [11, 65]
//현이 교차한다는 뜻은 각 구간이 교차한다는 뜻과 동일하다.
//따라서 이 문제를 교차하지 않는 구간의 최대 집합을 구하는 문제로 바꿔 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int SIZE = 101;
int N;
bool chord[SIZE][SIZE];
int dp[SIZE][SIZE]; //dp[i][j] : 구간 [i, j]에서 조건을 만족하는 현들의 최대집합

int solve(int s, int e)
{
    if(s == e) return 0;
    if(dp[s][e] != -1) return dp[s][e];
    
    int& ret = dp[s][e];
    //구간을 둘로 갈라, 두 구간에서 조건을 만족하는 현들의 최대집합의 합의 최댓값을 구한다.
    for(int i=s; i<e; i++) ret = max(ret, solve(s, i) + solve(i+1, e));
    
    if(chord[s][e]) return ++ret;
    else return ret;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
    cin >> N;
    for(int i=1; i<=N; i++)
    {
        int x, y; cin >> x >> y;
        if(x > y) swap(x, y);
        chord[x][y] = true;
    }
    
    memset(dp, -1, sizeof(dp));
    cout << solve(1, 100);
}

 

10266번: 시계 사진들 - KMP

//각도의 차의 순서가 서로 같은지 판별하는 문제이다.
//주어진 각도를 정렬한 후 각도 차를 계산해 저장한 배열을 각각 S, T라 하자. 우리는 T에서 S를 찾아야 한다.
//배열 S, T를 문자열로 본다면, 이 문제를 KMP를 이용해 해결할 수 있을 것이다.
//단, T는 원순열이므로 주의한다.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MAXN = 200000;
const int MAXA = 360000;
int n;
vector<int> s, t;
vector<int> S, T;
int back[MAXA];
int idx = -1;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n;
    for(int i=0; i<n; i++)
    {
        int si; cin >> si;
        s.push_back(si);
    }
    for(int i=0; i<n; i++)
    {
        int ti; cin >> ti;
        t.push_back(ti);
    }
    
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    
    //각도 차 계산
    for(int i=1; i<n; i++) S.push_back(s[i]-s[i-1]);
    S.push_back(s[0]+MAXA-s[n-1]);
    for(int i=1; i<n; i++) T.push_back(t[i]-t[i-1]);
    T.push_back(t[0]+MAXA-t[n-1]);
    
    //S에 대한 실패 함수
    back[0] = -1;
    int SIdx = 0;
    while(SIdx < n)
    {
        while(idx != -1 && S[SIdx] != S[idx]) idx = back[idx];
        back[++SIdx] = ++idx;
    }
    
    //KMP
    idx = 0;
    int TIdx = 0;
    bool chk = false;
    while(!(chk && TIdx >= idx)) //한 바퀴를 돌고 TIdx가 idx보다 크거나 같으면 안 된다.
    {
        while(idx != -1 && T[TIdx] != S[idx]) idx = back[idx];
        TIdx++, idx++;
        if(TIdx == n) TIdx = 0, chk = true; //한 바퀴 돌았는지 판별
        
        if(idx == n)
        {
            cout << "possible";
            exit(0);
        }
    }
    cout << "impossible";
}

 

10999번: 구간 합 구하기 2 - 세그먼트 트리(lazy)

https://oberon.tistory.com/275

10999번: 구간 합 구하기 2 - 세그먼트 트리(lazy)

 

11375번: 열혈강호 - 이분 매칭

https://oberon.tistory.com/260

11375번: 열혈강호 - 이분 매칭

 

13907번: 세금 - 최단 경로(다익스트라)

/*
S부터 D까지 최소의 가중치로 가야 하므로 이 문제는 최단 경로 문제이다.
하지만, 그냥 풀었다간 다익스트라를 3만 번 돌려야 하므로 다른 방법이 필요하다.

세금은 간선을 몇 번 거치냐에 따라 달라지므로, 기존의 dist 배열에서 간선을 몇 번 거쳤는지에
대한 정보를 추가하여 문제를 해결한다. 따라서 dist 배열을 다음과 같이 설정한다.
dist[i][j] : 간선을 i번 거쳐 정점 j에 도달했을 때의 최단 경로
이때 정점은 N개 밖에 없으므로 간선을 최대 N개도 지나지 못한다. 따라서 dist 배열의 공간 복잡도는 O(N^2)이다.
다익스트라로 이를 구하는 시간 복잡도는 O(N^2log(N^2))이다.

세금을 입력받을 때마다, dist[1~N][D]를 순회하며 최솟값을 구하면 된다.
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tll;

const ll INF = 1e18;
const ll MAXN = 1001;
const ll MAXK = 30001;
ll N, M, K;
ll S, D;

vector<pll> graph[MAXN];
ll dist[MAXN][MAXN];
priority_queue<tll, vector<tll>, greater<tll>> pq;

void dijkstra()
{
    fill(&dist[0][0], &dist[MAXN-1][MAXN], INF);
    dist[0][S] = 0;
    pq.push({0, 0, S});
    
    while(!pq.empty())
    {
        auto [d, m, u] = pq.top(); pq.pop();
        if(d > dist[m][u] || m == MAXN-1) continue;
        
        for(auto [d, v] : graph[u])
        {
            if(dist[m+1][v] > dist[m][u] + d)
            {
                dist[m+1][v] = dist[m][u] + d;
                pq.push({dist[m+1][v], m+1, v});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M >> K;
    cin >> S >> D;
    while(M--)
    {
        int a, b, w; cin >> a >> b >> w;
        graph[a].push_back({w, b});
        graph[b].push_back({w, a});
    }

    dijkstra();

    ll tax = 0;
    while(true)
    {
        ll ans = INF;
        for(ll i=1; i<MAXN; i++) ans = min(ans, i * tax + dist[i][D]);
        cout << ans << "\n";
        
        if(!K--) break;
        
        int p; cin >> p;
        tax += p;
    }
}

 

16975번: 수열과 쿼리 21 - 세그먼트 트리

https://oberon.tistory.com/83

16975번: 수열과 쿼리 21 - 세그먼트 트리

 

16978번: 수열과 쿼리 22 - 세그먼트 트리, 오프라인 쿼리

https://oberon.tistory.com/277

16978번: 수열과 쿼리 22 - 세그먼트 트리, 오프라인 쿼리

 

18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) - 그래프(DFS), 스위핑, DP

//y좌표는 20을 넘지 않고, x좌표는 그래프를 중위 순회하면 된다.
//y좌표의 범위가 작기에 y좌표의 구간을 제한하면서, 구간의 부분합의 최댓값을 구하면 된다.
//부분합의 최댓값은 DP를 이용해 O(N)에 구할 수 있고, y좌표의 구간 제한은 O((logN)^2)가 걸린다.
//전체 시간 복잡도 O(N(logN)^2)에 답을 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int INF = 1e9;
const int MAXN = 300000;
int N, K = 1;
ll W[MAXN];

vector<pll> sweep[20];
ll val[MAXN], dp[MAXN];

int DFS_cnt = 1;

void DFS(int u, int d)
{
    if(d > K) return;
    
    DFS(u*2, d+1);
    sweep[d].push_back({W[u], DFS_cnt++});
    DFS(u*2+1, d+1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    
    cin >> N;
    for(int i=1; i<=N; i++) cin >> W[i];
    
    //가중치가 전부 음수일 때를 예외 처리한다.
    ll mx = -INF;
    bool chk = false;
    for(int i=1; i<=N; i++)
    {
        if(W[i] > 0) chk = true;
        mx = max(mx, W[i]);
    }
    if(!chk)
    {
        cout << mx;
        exit(0);
    }
    
    while(pow(2, K) - 1 != N) K++;
    DFS(1, 1); //중위 순회
    
    ll ans = -INF;
    for(int L=1; L<=K; L++) //왼쪽 구간
    {
        memset(val, 0, sizeof(val));
        for(int R=L; R<=K; R++) //오른쪽 구간
        {
            for(auto [v, idx] : sweep[R]) val[idx] = v;
            
            memset(dp, 0, sizeof(dp));
            for(int i=1; i<=N; i++) 
            {
            	//dp[i] : 구간의 오른쪽 끝이 i일 때 구간합의 최댓값
                if(dp[i-1] < 0) dp[i] = val[i]; //dp[i-1]이 음수면 지금까지 구한 구간합을 더할 이유가 없다.
                else dp[i] = dp[i-1] + val[i];
            }
            for(int i=1; i<=N; i++) ans = max(ans, dp[i]);
        }
    }
    cout << ans;
}

 

24505번: blobhyperthink - 세그먼트 트리, DP

https://oberon.tistory.com/288

17409번: 증가 수열의 개수 - 세그먼트 트리, DP

//위 문제에서 중복 처리만 하면 된다.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MAXN = 100001;
const int MOD = 1e9+7;
int N;
ll dp[MAXN][12];
int A[MAXN];
ll segTree[MAXN*4];

void update(int s, int e, int m, int idx, ll val)
{
    if(m < s || e < m) return;
    if(s == e)
    {
        segTree[idx] += val; //단순히 값을 더하는 것으로 바꾸면 된다.
        segTree[idx] %= MOD;
        return;
    }
    
    update(s, (s+e)/2, m, idx*2, val);
    update((s+e)/2+1, e, m, idx*2+1, val);
    segTree[idx] = (segTree[idx*2] + segTree[idx*2+1]) % MOD;
}

ll sum(int s, int e, int l, int r, int idx)
{
    if(e < l || r < s) return 0;
    if(l <= s && e <= r) return segTree[idx];
    return (sum(s, (s+e)/2, l, r, idx*2) + sum((s+e)/2+1, e, l, r, idx*2+1)) % MOD;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N;
	for(int i=1; i<=N; i++)
	{
	    cin >> A[i];
	    dp[i][1] = 1;
	}
	
	for(int k=2; k<=11; k++)
	{
	    memset(segTree, 0, sizeof(segTree));
	    for(int i=1; i<=N; i++)
	    {
	        update(1, N, A[i], 1, dp[i][k-1]);
	        dp[i][k] = sum(1, N, 1, A[i]-1, 1);
	    }
	}
	
	ll ans = 0;
	for(int i=1; i<=N; i++)
	{
	    ans += dp[i][11];
	    ans %= MOD;
	}
	cout << ans;
}