백준: Class 5 - 9252, 1806, 1987

</br> 클래스 5 계속
</br>

9252: LCS 2

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

    for(int i = 1; i <= s1.size(); i++){
        for(int j = 1; j <= s2.size(); j++){
            if( s1[i-1] == s2[j-1] ) dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
            dp[i][j] = max({dp[i][j], dp[i][j-1], dp[i-1][j], dp[i-1][j-1]});
        }
    }
    stack<char> st;
    int i = s1.size();
    int j = s2.size();
    while( i && j ){
        if( dp[i][j] == dp[i-1][j] ){
            i--;
        }
        else if( dp[i][j] == dp[i][j-1] ){
            j--;
        }
        else{
            st.push(s1[i-1]);
            i--;
            j--;
        }

    }
    cout << dp[s1.size()][s2.size()] << endl;
    while( st.size() ){
        cout << st.top();
        st.pop();
    }
    cout << endl;

저번 포스트(9251: LCS, https://cyj893.github.io/algorithm/Algorithm16_9/)에서 또 역추적해서 복구하기다

ACAYKP
CAPCAK

ACAK
  C A P C A K
A 0 [1] 1  1  1  1
C 1  1  1 [2] 2  2
A 1  2  2  2 [3] 3
Y 1  2  2  2  3  3
K 1  2  2  2  3 [4]
P 1  2  3  3  3  4

잘 보면 저런 표시한 부분, 즉 대각선과 숫자가 바뀔 때를 골라주면 된다.
</br>

1806: 부분합

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

    for(int i = 0; i < n; i++){
        cin >> nums[i];
        if( nums[i] >= s ){
            cout << 1 << endl;
            return 0;
        }
    }

    int ans = INT_MAX;
    int sum = nums[0] + nums[1];
    int l = 0, r = 1;
    while( l < r && r < n ){
        if( sum < s ){
            r++;
            sum += nums[r];
        }
        else{
            ans = min(ans, r-l+1);
            sum -= nums[l];
            l++;
        }
    }

    if( ans == INT_MAX ) cout << 0 << endl;
    else cout << ans << endl;

투 포인터로 풀 수 있는 문제였다
일단 입력 받으면서 하나로도 가능하면 1을 출력하고 바로 종료한다.
그게 아니면 포인터를 각 0, 1에 두고 시작한다(1은 확인했으므로 2부터)
합이 모자라면 r을 오른쪽으로, 합이 넘으면 l을 오른쪽으로 해서 슬라이딩하며 끝까지 넘어가면 된다.

ex) 10 15
5 1 3 5 7 4 10 3 2 8


5 1 3 5 7 4 10 3 2 8
l r
sum = 6

5 1 3 5 7 4 10 3 2 8
l   r
sum = 9

5 1 3 5 7 4 10 3 2 8
l     r
sum = 14

5 1 3 5 7 4 10 3 2 8
l       r
sum = 21  < ans = 5

5 1 3 5 7 4 10 3 2 8
  l     r
sum = 16  < ans = 4

5 1 3 5 7 4 10 3 2 8
    l   r
sum = 15  < ans = 3

5 1 3 5 7 4 10 3 2 8
      l r
sum = 12

5 1 3 5 7 4 10 3 2 8
      l   r
sum = 16  < ans = 3

...

</br>

1987: 알파벳

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

void func(int x, int y, int d){
    ans = max(ans, d);
    visited[x][y] = 1;
    visitalpha[mmap[x][y]-'A'] = 1;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if( nx < 0 || r <= nx || ny < 0 || c <= ny || visited[nx][ny] || visitalpha[mmap[nx][ny]-'A'] ) continue;
        func(nx, ny, d+1);
        visited[nx][ny] = 0;
        visitalpha[mmap[nx][ny]-'A'] = 0;
    }
}

// in main()
    func(0, 0, 1);
    cout << ans << endl;

간만에 쉬운 dfs다
일단 기본 dfs처럼 visited 체크하고 그런데, 이미 방문한 알파벳인지만 추가해서 확인해 주면 끝
</br>

---

열심히 하자
</br>