프로그래밍

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=393&sw_prbl_sbms_sn=18407

[난이도] level4
[유형] DP

[풀이]
이전 포스팅의 징검다리 문제보다 어려운 문제입니다.
이유는 아래와 같습니다.
1. N 제한이 10만을 넘어가므로 LIS를 구할 때 lower_bound를 이용하는 O(NlogN) 방법을 이용해야 합니다.
2. 단순 LIS를 구하는 것이 아닌 증가했다가(LIS) 감소하는(LDS) 변곡점이 있는 LIS + LDS sequence를 구해야 합니다.

0~N-1 번 돌을 변곡점으로 확정짓고 그 점부터 좌우로 퍼져나가는 LIS 혹은 LDS를 구하려고 하면 O(N^2logN)이 되어 시간초과에 빠지게 됩니다.

그러므로 앞에서부터 LIS를 한번 구해서 정보들을 저장 한 뒤, 뒤에서부터 LIS를 구해주면서
앞에서부터 LIS를 구해주면서 저장한 정보를 이용해 답을 구하는 O(NlogN) 해법을 이용해야 합니다.

아래 코드에서는 asc[300000], ascmax[300000] 배열을 선언하여 사용하였습니다.
asc[i] : 0~i 돌을 사용한 LIS의 크기.
ascmax[i] : 0~i 돌을 사용한 LIS의 마지막 값.

앞에서부터 LIS를 구하면서 위의 정보를 저장 한 뒤,

뒤에서부터 LIS를 돌려줍니다.
만약 i번 돌이 변곡점이 된다면 포함될 수 있는 최대 돌의 개수는
int v = dp.size() (N-1~i 돌을 사용한 LIS의 크기) + asc[i] (0~i 돌을 사용한 LIS의 크기)
이 됩니다.

하지만 여기서 예외처리 해주어야 할 것이 i번 돌이 좌측 LIS, 우측 LIS에 모두 포함될 경우입니다.
이 경우에는 변곡점 i번 돌을 1개 빼주어야 하므로
ascmax[i]를 확인해서 a[i]와 같은지, dp.back() (현재 LIS의 가장 큰 값) 이 a[i]와 같은지를 모두 체크해서
둘다 같다면 v-- 연산을 해주면 됩니다.

이는 모든 돌의 높이가 다르다는 것이 문제의 조건에 나와있기 때문에 가능합니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int ans,N,a[300001],asc[300001],ascmax[300001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);

    vector<int> dp = {a[0]};

    for(int i=1;i<N;i++){
        int idx = lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        if(idx == dp.size()) dp.push_back(a[i]);
        else dp[idx]=a[i];
        asc[i]=dp.size();
        ascmax[i]=dp.back();
    }

    dp.clear();
    dp.push_back(a[N-1]);

    for(int i=N-2;i>=0;i--){
        int idx = lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        if(idx == dp.size()) dp.push_back(a[i]);
        else dp[idx]=a[i];
        int v = dp.size()+asc[i];
        if(ascmax[i]==a[i] && dp.back()==a[i]) v--;
        ans=max(ans,v);        
    }
    printf("%d",ans==0?1:ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/징검다리2.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=390&sw_prbl_sbms_sn=18384

[난이도] level3
[유형] DP

[풀이]
LIS(Longest Increasing Subsequence) 다이나믹 프로그래밍 문제입니다.
돌계단의 높이가 높아지는 순서로 선택하고, 그 개수를 최대로 해야하기 때문입니다.
N 제한 3000이기 때문에 O(N^2) 시간복잡도 풀이로 해결이 가능합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,a[3001],dp[3001];
int sol(int n){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=n+1;i<=N;i++)
        if(a[n]<a[i]) ret=max(ret,1+sol(i));
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/징검다리.cpp

https://programmers.co.kr/learn/courses/30/lessons/72416

[난이도] level4
[유형] DP

[풀이]
sales 배열의 크기가 최대 300000 이므로 판매원을 참석시킬 수 있는 모든 케이스를
다 해보기에는 시간이 너무 오래걸리기 때문에 다이나믹 프로그래밍을 사용해야 합니다.

우선 주어진 입력을 이용해 2차원 tree vector에 tree[parent].push_back(child) 와 같이
트리 형식으로 저장해줍니다.

Top-Down 방식을 이용하였고 sol(n)은 DP[n]은 구하고 return 합니다.

DP 배열은 아래와 같이 간단히 정의합니다.
DP[n] : 루트가 n인 트리의 최소 비용.

루트가 n일때,  루트인 n 혹은 그 자식 노드중에 하나는 회의에 참석해야 합니다.
위의 케이스를 모두 계산해보고 그 중 최솟값을 DP[n]의 값으로 확정짓는 방식으로 DP[n]을 구합니다.

우선 풀이에 사용될 변수 v를 아래와  같이 정의합니다.
v : n의 자식 노드가 nxt일 때 모든 DP[nxt]의 합
v = sum(DP[nxt])

점화식은 아래와 같습니다.
DP[n] = 

        i) n을 회의에 참석 시킬 때,
            n을 참석 시킬 때 비용 sales[n]에 n의 자식 노드들의 최소비용을 더해주기만 하면 되므로
            v + sales[n] 이 됩니다.

        ii) n의 자식 중 하나인 nxt를 회의에 참석 시킬 때,
            root인 n은 참여하지 않았으므로 sales[n]은 더할 필요 없이
            일단 v 값에 sales[nxt]를 더해줍니다.
            v값은 업데이트 되면 안되므로 임시변수 t를 선언하였습니다.
            t = v+sales[nxt]

            여기서 v에 더해져 있던 sol(nxt) 값은 nxt가 회의에 참석 되는 것이 확정되었으므로
            t에 빼주어야 합니다. 왜냐하면 sol(nxt)에는 nxt가 참여한 경우, 참여하지 않은 경우가 모두
            포함되어 있기 때문입니다.
            t = v+sales[nxt]-sol(nxt)

            여기까지 해주면 nxt의 자식들이 nnxt라고 했을 때, sol(nnxt)의 값도 빠져버려 nxt 자식 트리들의
            비용은 반영이 안되어 버리기 때문에 sol(nnxt)의 값들은 다시 더해줘야 합니다.
            t = v+sales[nxt]-sol(nxt)+sum(sol(nnxt)) (nnxt는 nxt의 자식노드들)
            위의 t 값이 nxt를 회의에 참여 시켰을 때의 최솟값이 됩니다.

        만약 sol(n)에서 n의 자식이 없다면 회의에 참석할 필요가 없기 때문에 0을 return 합니다.

        최종 DP[n]은 i),ii) 케이스 둘에서 나온 값들 중에 최솟값이 됩니다.

#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
vector<int> sales,tree[300001];
int dp[300001],inf=1<<31-1;
int sol(int n){
    if(tree[n].empty()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;

    ret=inf;
    int v=0;
    for(int nxt : tree[n]) v+=sol(nxt);
    ret=min(ret,v+sales[n-1]);
    for(int nxt : tree[n]){
        int t = v-sol(nxt);
        t+=sales[nxt-1];
        for(auto nnxt : tree[nxt]) {
            if(!tree[nnxt].empty()) t+=sol(nnxt);
        }
        ret=min(ret,t);
    }
    return ret;
}
int solution(vector<int> _s, vector<vector<int>> links) {
    sales = _s;
    memset(dp,-1,sizeof(dp));
    for(auto l : links) tree[l[0]].push_back(l[1]);
    return sol(1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/매출_하락_최소화.cpp

https://programmers.co.kr/learn/courses/30/lessons/12942

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍으로 해결할 수 있씁니다.
DP[i][j] : i~j 구간의 행렬을 계산했을 때의 최솟값.
DP[i][j] = min(DP[l][i]+DP[i+1][r]+matrix[l][0]*matrix[i][1]*matrix[r][1]) (l<=i<r)

#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> matrix;
int dp[201][201];
int sol(int l,int r){
    if(l==r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = 2e9;
    for(int i=l;i<r;i++) ret=min(ret,sol(l,i)+sol(i+1,r)+matrix[l][0]*matrix[i][1]*matrix[r][1]);
    return ret;
}
int solution(vector<vector<int>> matrix_sizes) {
    matrix=matrix_sizes;
    memset(dp,-1,sizeof(dp));
    return sol(0,matrix.size()-1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/최적의_행렬_곱셈.cpp

https://programmers.co.kr/learn/courses/30/lessons/1843

[난이도] level4
[유형] DP

[풀이]
연산자의 수가 최대 N=100개가 될 수 있으므로 이것을 순열로 만들어 모든 연산 순서에
대해 해보는 풀이로는 해결할 수 없습니다.

다이나믹 프로그래밍을 이용하면 O(N^2)의 복잡도로 해결이 가능합니다.

재귀를 이용한 Top-Down DP를 이용하였으며

sol(int l,int r,int k) 함수는 dp[l][r][k]를 구하며 리턴합니다.

정의는 아래와 같습니다.
dp[l][r][k] : if k==0
                l~r번째 연산자 구간의 연산결과의 최솟값
              if k==1
                l~r번째 연산자 구간의 연산결과의 최댓값

배열의 길이가 2n+1 이라면 연산자는 총 n개 존재하며 각 연산자는 0~n-1 index를 갖는다고 가정합니다.

만약 아래와 같은 배열이 있다면 "-","-","+"연산자는 각각 index 0,1,2 입니다.
["1","-","5","-","3","+","8"]

l~r번째 연산자 구간의 의미는 전체 배열 arr에서는 arr[2*l] , arr[2*l+1] ... arr[2*r+2] 를 모두 사용했을 때,
즉 2*l~2*r+2 구간의 모든 숫자와 연산자를 사용했을 때의 최소 혹은 최댓값을 의미합니다.

예를들어, ["1","-","5","-","3","+","8"] 에서 1~2번째 연산자 구간의 값을 구하는 것은
("5","-","3","+","8")를 모두 사용한 값을 구하는 것이므로 arr[2*1] ~ arr[2*2+2] 를 모두 사용하는 것을 의미합니다.

dp[l][r][k] 를 구하려면

l~r 구간을 어떤 연산자를 기준으로 나눌지를 정해야 합니다.
만약 l이상 r이하의 i로 구간을 나눈다면

k가 0,1인 경우, arr[2*i+1]가 "+","-"인 경우가 나눠지므로 총 4가지 케이스의 식이 나옵니다.

a) k==0
    a-1) arr[i]=="+"
        sol(l,r,k) = sol(l,i-1,0) + sol(i+1,r,0)
        위와 같이 구할 수 있습니다. l~i-1 연산자 구간, i+1~r 연산자 구간의 최댓값 구하면 됩니다.
        만약 l>i-1 인 경우 좌측에 더이상 연산자가 없다는 의미이므로 arr[2*l] 값을 그대로 사용하면 되고,
        i+1>r 인 경우도 역시 우측에 더이상 연산자가 없다는 의미이므로 arr[2*r+2] 값을 그대로 사용하면 됩니다.
        이는 다른 케이스에서도 동일하게 적용됩니다.

        arr[i]=="+" 이므로 더하기 연산을 해야하는데 k==0으로, 최솟값을 구해야 하므로
        l~i-1 구간의 최솟값, i+1~r 구간의 최솟값을 더하는 것이 최솟값을 구할 때 가장 최적이므로
        sol(l,i-1,0) + sol(i+1,r,0) 와 같이 최솟값을 구하기 위해 3번째 인자로 0을 넣어주었습니다.

    a-2) arr[i]=="-"
        sol(l,r,k) = sol(l,i-1,0) + sol(i+1,r,1)

        첫번째 케이스와 마찬가지로 lvalue - rvalue 형태가 나와야 하는데 최솟값이 되려면
        lvalue는 최소, rvalue는 최대가 되는 것이 최적입니다.
        그러므로 위와 같은 식이 나옵니다.

    모든 i에 대해 위와 같이 식을 구해본 뒤 나온 값을 중에 "최솟"값이 sol(l,r,k) 의 최종 결과가 됩니다.

b) k==1
    b-1) arr[i]=="+"
        sol(l,r,k) = sol(l,i-1,1) + sol(i+1,r,1)
        lvalue + rvalue형태이므로 lvalue는 최대, rvalue는 최대인 것이 최댓값을 만들 때 최적입니다.

    b-2) arr[i]=="-"
        sol(l,r,k) = sol(l,i-1,1) + sol(i+1,r,0)
        lvalue + rvalue형태이므로 lvalue는 최대, rvalue는 최소인 것이 최댓값을 만들 때 최적입니다.

    모든 i에 대해 위와 같이 식을 구해본 뒤 나온 값을 중에 "최댓"값이 sol(l,r,k) 의 최종 결과가 됩니다.

#include <vector>
#include <string>
#include <cstring>
using namespace std;
int dp[101][101][2],inf=9e8;
vector<string> arr;
int sol(int l,int r,int k){
    int& ret = dp[l][r][k];
    if(ret!=-1) return ret;
    if(k){
        ret=-inf;
        for(int i=l;i<=r;i++){
            int lv,rv;
            lv = l>i-1 ? stoi(arr[2*l]) : sol(l,i-1,1);
            if(i+1>r) rv = stoi(arr[2*r+2]);
            else if(arr[2*i+1]=="+") rv = sol(i+1,r,1);
            else rv = sol(i+1,r,0);

            if(arr[2*i+1]=="+") ret=max(lv+rv,ret);
            else ret=max(lv-rv,ret);
        }
    }else{
        ret=inf;
        for(int i=l;i<=r;i++){
            int lv,rv;
            lv = l>i-1 ? stoi(arr[2*l]) : sol(l,i-1,0);
            if(i+1>r) rv = stoi(arr[2*r+2]);
            else if(arr[2*i+1]=="+") rv = sol(i+1,r,0);
            else rv = sol(i+1,r,1);

            if(arr[2*i+1]=="+") ret=min(lv+rv,ret);
            else ret=min(lv-rv,ret);
        }        
    }
    return ret;
}

int solution(vector<string> _arr)
{
    memset(dp,-1,sizeof(dp));
    arr=_arr;
    return sol(0,arr.size()/2-1,1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/사칙연산.cpp

https://programmers.co.kr/learn/courses/30/lessons/12983

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 문제를 해결할 수 있습니다.

dp 배열을 선언하여 아래와 같이 정의합니다.
dp[i] = 문자열 t의 i번째 문자부터 시작하는 문자열을 만들 때 필요한 단어 조각의 최솟값.

Top-down DP를 이용하였습니다.

dp[n]을 구하고 리턴하는 sol(n)은 아래와 같은 과정을 통해 구해집니다.

for(auto& s : str){
    if(check(n,s)) ret=min(sol(n+s.size()),ret);
}
return ++ret;

str의 모든 단어 조각 s들을 확인하면서 t의 n번 index부터 시작하는 부분 문자열을 대체할 수 있는지를 체크합니다.
대체할 수 있다면 sol(n)=1+sol(n+s.size()) 으로 업데이트 할 수 있습니다. 하지만 이 값이 최솟값인지는 알 수 없기 때문에
모든 s들을 확인하면서 min값으로 업데이트 해줍니다. 위의 코드에서는 +1은 return 시에 해주었습니다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<string> str;
string t;
int dp[20001],inf=9e7;;
bool check(int n,string& s){
    for(int i=0;i<s.size();i++){
        if(n+i>=t.size()) return 0;
        if(t[n+i]!=s[i]) return 0;
    }
    return 1;
}
int sol(int n){
    if(n==t.size()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=inf;
    for(auto& s : str){
        if(check(n,s)) ret=min(sol(n+s.size()),ret);
    }
    return ++ret;
}
int solution(vector<string> _strs, string _t){   
    memset(dp,-1,sizeof(dp));
    str=_strs;
    t=_t;
    return sol(0) >= inf ? -1 : sol(0);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/단어_퍼즐.cpp

https://programmers.co.kr/learn/courses/30/lessons/12971

[난이도] level3
[유형] DP

[풀이]
첫번째 스티커를 떼면 마지막 N번째 스티커는 절대로 뗄 수 없고,
첫번째 스티커를 떼지 않으면 마지막 N-1번째 스티커에 따라 뗄 수 있을수도 없을수도 있습니다.

이를 이용해 첫번째 스티커를 뗀 경우와 안뗀 경우를 나눠서 생각하면 편합니다.

dp[n][f] 배열에서 f가 0이면 첫번째 스티커를 뗀 경우, 1이면 떼지 않은 경우로 생각하여 문제를 풉니다.

dp[n][f] (sol(n,f)) 의 의미는 n~N-1까지만 고하고, n번째 스티커는 뗄수도 있을 때, 얻을 수 있는 최댓값입니다.

top-down으로 진행했을 때 점화식은 아래와 같습니다.
sol(n,f) = max(sticker[n]+sol(n+2,f),sol(n+1,f))

sticker[n]+sol(n+2,f) : n번째 스티커를 뗐을 때입니다. n번 스티커의 수에 n+1번째 스티커는 뗄 수 없으므로 sol(n+2,f)를 더해줍니다.
sol(n+1,f) : n번째 스티커를 떼지 않았을 때이므로 1 건너뛰어 sol(n+2,f) 입니다.

마지막으로 n이 N-1이 되었을 때, f가 1이면 N-1번 스티커는 떼지 못하므로 0을 return, 0이면 뗄 수 있으므로 sticker[N-1]를 return 해줍니다.

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N,dp[100002][2];
vector<int> sticker;
int sol(int n,int f){
    if(n>=N) return 0;
    if(n==N-1) return f ? 0 : sticker[N-1];
    int& ret = dp[n][f];
    if(ret!=-1) return ret;
    ret=max(sticker[n]+sol(n+2,f),sol(n+1,f));
    return ret;
}
int solution(vector<int> _sticker)
{
    sticker=_sticker;
    N=sticker.size();
    memset(dp,-1,sizeof(dp));
    return max(sol(1,0),sol(2,1)+sticker[0]);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스티커_모으기(2).cpp

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

[난이도] Silver1
[유형] DP

[풀이]
입력을 받으면서 sum[i][j]에 (1,1)~(i,j)까지의 합을 저장합니다.
현재 입력은 (i,j)의 값이 r[j-1]일때, sum[i][j]는 아래와 같이 구할 수 있습니다.
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+r[j-1]
sum[i-1][j-1]이 두번 두해졌기 때문에 한번 빼는 것입니다.

쿼리 (x1,y1)~(x2,y2) 은 아래와 같이 구할 수 있습니다.
sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1]
이번엔 반대로 sum[y1-1][x1-1]이 두번 빠졌으므로 한번 더해주는 것입니다.

println을 사용하면 시간초과가 나서 bufferedWriter를 이용해야 했습니다.

import java.util.*
val bw = System.`out`.bufferedWriter()
var sum = Array(1025){IntArray(1025)}
fun main() = with(System.`in`.bufferedReader()){
    val (N,M) = readLine().split(' ').map{it.toInt()}
    for(i in 1..N){
        val r = readLine().split(' ').map{it.toInt()}
        for(j in 1..N)  sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+r[j-1]
    }
    repeat(M){
        val (y1,x1,y2,x2) = readLine().split(' ').map{it.toInt()}
        val ret = sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1]
        bw.write(ret.toString()+'\n')
    }
    bw.flush()
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/11660.cpp