p0her

스택의 괄호쌍 유형의 응용 버전.

처음에 괄호 안에 괄호가 들어있는 형태랑 닫힌 괄호 옆에 새로운 괄호가 있는 경우를 판단하는게 너무 어려웠다.그래서 보니까 일단 열린 괄호가 '(' 면 2를 곱해놓고 '[' 면 3을 곱해놓은 다음에, 스택에 문자를 넣는다.그리고 열린 괄호가 계속 나올때 까지 해당 괄호에 해당하는 숫자를 계속 곱하다가, 닫는 괄호가 나올 때가 중요한데, 한번 닫는 괄호가 나오면 지금까지 열린 괄호 만큼 곱해준걸 ans변수에 더한다. (이러면 이전 괄호 개수만큼 값을 고려할 수 있음)

그리고 닫는 만큼 계속 나눠주다가 다시 열린게 나오면 반복... 그 외에 경우는 모두 괄호쌍이 맞지 않으니까 ans = 0 넣어놓고 탈출하면 된다. 그리고 저 과정을 거쳐도 스택이 모두 안 비어질때가 있는데 그 땐 올바르지 않으니까 empty인지 체크하고 0 넣어주면 된다.

#include <bits/stdc++.h>
using namespace std;
string x;
stack<int> s;
int ans;
void solve() {
    int tmp = 1;
    char pre = ' ';
    for(int i = 0; i < x.length(); i++) {
        if(x[i] == '(' || x[i] == '[') {
            s.push(x[i]);
            if(x[i] == '(') tmp *= 2;
            else tmp *= 3;
        } else {
            if(x[i] == ')') {
                if(s.empty()) {
                    ans = 0;
                    break;
                }
                if(s.top() == '[') {
                    ans = 0;
                    break;
                }
                s.pop();
                if(pre == '(') {
                    ans += tmp;
                    tmp /= 2;
                } else {
                    tmp /= 2;
                }
            } else {
                if(s.empty()) {
                    ans = 0;
                    break;
                }
                if(s.top() == '(') {
                    ans = 0;
                    break;
                }
                s.pop();
                if(pre == '[') {
                    ans += tmp;
                    tmp /= 3;
                } else  {
                    tmp /= 3;
                }
            }
        }
        pre = x[i];
    }    
    if(!s.empty()) cout << 0;
    else cout << ans;
}
int main() {
    cin >> x;
    solve();
}

#include <bits/stdc++.h>
using namespace std;
int N, M, a[41];
int dp[41];
int ans = 1;
int main() {
    cin >> N;
    cin >> M;
    for(int i = 0; i < M; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    int cnt = 1;
    int s = 0;
    for(int i = 3; i <= 40; i++) dp[i] = (dp[i-1] + dp[i-2]);
    for(int i = 0; i < M; i++) {
        int e = a[i];
        ans *= dp[e - s - 1];
        s = e;
    }
    ans *= dp[N - s];
    cout << ans;
}

$D[i]$ 를 vip석 없이 1~i 를 배치하는 경우의 수라고 점화식을 정의하자. 그러면 두 가지 케이스로 나눠야하는데,

1. $i$번째 좌석에 $i$번 사람이 앉을 때 => 이 때는 그냥 $i-1$ 번째만 잘 앉으면 되니까 $D[i-1]$

2. $i$ 번째 좌석에 $i-1$번 사람이 앉을 때 => 이 땐 $D[i-1]$ 이랑 $D[i]$ 가 고정이다. (둘이 바꿨으니까) 그러면 $D[i-2]$ 만 잘 앉으면 된다.

즉 $D[i] = D[i-1] + D[i-2]$ 인데, vip 석이 문제다. 근데 vip 석이 생길 때 마다 연속으로 앉는 자리의 개수가 초기화 되니까 , vip 석 사이의 거리를 계산해주면 된다.

#include <bits/stdc++.h>
using namespace std;
int N, dp[1000001], A[1000001];

int main() {
    cin >> N;
    dp[1] = 0;
    A[1] = -1;
    for(int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;
        A[i] = i - 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
            dp[i] = min(dp[i] , dp[i / 2] + 1);
            A[i] = i / 2;
        }
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
            A[i] = i / 3;
        }
    }
    cout << dp[N] << '\n';
    for(int i = N; i >= 1; i = A[i]) {
        cout << i << ' ';
    }
}

DP 역추적 기본 문제이다. 1로 만들기 문제랑 비슷하게 풀면 되는데, 1로 만드는 방법의 경로들을 출력해야 하므로 이 경로들을 저장하는 배열들이 하나 필요하다. 그래서 배열에 이전에 왔던 경로들을 저장하면 되는데, 이 때 dp 배열의 값을 비교해서 이전 dp 배열보다 더 적은 횟수면 경로를 저장해줘야한다.

DP 기본 문제이다.

$O(N^2)$ 으로 풀 수 있는데, 원소를 하나 택하고, 그 전 원소들을 돌아보면서 현재 원소보다 작으면 이걸 더하면 된다. 

근데 이러면 1, 1, 2 같은 상황이 문제가 생기는데 그럼 1, 1은 증가하는 수열이 아닌데 2 기준에선 1, 1에서 증가하기 때문에 1 + 1 + 2 = 4 가 답이 나오게 된다. 그래서 dp 배열이 하나 필요한데, $dp[i]$ 를 i번째 원소를 더했을 때 가장 큰 증가하는 부분 수열 이라고 정의 하자.그럼 i번째 원소 이전에 j번째 원소를 돌아볼 때 합이 가장 큰 애만 더해줄 수 있고, 1, 1 과 같이 똑같은 수가 중복되는 상황도 해결할 수 있다. (dp[2] = 1, dp[1] = 1이 되니까). 

#include <bits/stdc++.h>
using namespace std;
int N, A[1001], dp[1001];
void solve() {
    int ans = 0;
    for(int i = 0; i < N; i++) {
        dp[i] = A[i];
        for(int j = 0; j < i; j++) 
            if(A[j] < A[i] && dp[i] < dp[j] + A[i])
                dp[i] = dp[j] + A[i];
        ans = max(ans, dp[i]);
    }
    cout << ans;
}
int main() {
    cin >> N;
    for(int i = 0; i < N; i++) cin >> A[i];
    solve();
}

sort 함수 연습용 문제. sort의 세 번째 인자에 bool형 함수를 넣으면 이 함수의 내용대로 sort 해준다.

#include <bits/stdc++.h>
using namespace std;
int N;
vector<string> A;
string x;

int f(string a) {
    int ret = 0;
    for(int i = 0; i < a.length(); i++) 
        if('0' <= a[i] && a[i] <= '9') ret += (a[i] - '0');
    return ret;
}
bool cmp(const string &a, const string &b) {
    int p, q;
    if(a.length() != b.length()) {
        return a.length() < b.length();
    } else if(a.length() == b.length()) {
        p = f(a);
        q = f(b); 
    }
    if(p != q) return p < q;
    return a < b;
}
int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> x;
        A.push_back(x);
    }
    sort(A.begin(), A.end(), cmp);
    for(int i = 0; i < N; i++) {
        cout << A[i] << '\n';
    }
}

cmp 함수만 보면 된다

1. 두 문자열의 길이가 같으면 더 긴걸 뒤로 보내야 하므로 a.length() < b.length()

2. 같으면 이 문자열중 숫자들만 더해서 더 큰걸 뒤로 보냄

3. 위에 두 개로 비교를 못하면 사전순 비교. (a<b) 여기서 비교를 못 한다는건 숫자가 없다는거니까 그냥 p,q 가 둘 다 0이니까 같은걸로 비교하면 됨

이분탐색에서 자주 쓰이는 테크닉이므로 기억해두자.

이 문제는 $a[i] + a[j] + a[k] = a[l]$ 에서 $a[l]$ 이 최대가 되는 $a[l]$ 을 출력해야한다. 

맨 처음 생각할 수 있는건 $O(N^4)$ 방법인데 당연히 시간초과가 나므로 pass. 그 다음은 $O(N^3log{N})$ 으로 먼저 $(i,j,k)$ 쌍 들을 모두 돌아보면서 이 합에 대해 $a[l]$ 을 이분탐색 하는 방법이 있다. 하지만 이것도 시간초과가 난다. 

이제 여기서 쓸 수 있는 테크닉이, 2개의 값을 묶어서 하나의 값에 대해 이분탐색을 돌려주면 된다.

이게 가능한 이유는 우리는 어차피 $(i,j,k)$ 쌍들은 상관 없고 정답을 만족 시키는 $a[l]$ 에만 관심이 있기 때문에, 미리 전 처리 해놓는거랑 비슷하다고 보면 된다. 그럼 $O(N^2log{N})$ 에 해결이 가능하다. 아마 문제를 많이 안 풀어봐서 모르지만 n개의 값을 묶어서 응용할 수 있을 것 같은데 좀 더 풀어보면 알거같다.

수 찾기 문제 + 같은 수가 얼마나 존재하는가 찾는 문제이다. 이 문제는 저번 문제 + 카운팅을 그대로 해주면 최악의 상황엔 같은 수가 N개가 있으면 시간 초과가 나기 때문에, 다른 방법을 생각해보아야 하는데 여기서 쓸 수 있는 테크닉이 있다. 

이분 탐색? 인지 단조 증가하는 수열의 성질인지 잘 모르겠으나 정렬하고 나면 같은 수들 끼린 붙어있게 되어있다. 여기서 맨 왼쪽에 있는 수와 맨 오른쪽에 있는 수의 index의 차를 구해주면, 결국 그것이 같은 수들의 개수가 된다. 이것을 각 각 lower_bound, upper_bound 라고 하는데, 그러므로 upper_bound - lower_bound 를 구해주면 그것이 정답이다.

먼저 naive 한 방법을 생각하자. M개의 수들에 대해 N개의 정수중 알맞는 수가 존재하는지 보려면 N개의 수를 모두 보면 되므로 O(NM) 이다. 하지만 이러면 시간 초과가 나서 시간 복잡도를 줄일 방법을 생각해보자. 먼저 sort를 해준 뒤 binary search를 이용하면 O(NlogN + MlogN) 이 되기 때문에 시간초과를 통과할 수 있다.