[BOJ] LCS(9251)

[๋ฐฑ์ค€(BOJ)] LCS(9251) C++

๋ฌธ์ œ : BOJ_9251๋ฒˆ LCS

๋ฌธ์ œ ์„ค๋ช…

DP

์ตœ๋Œ€ 1000 ๊ธ€์ž์˜ ๋‘ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๋‘ ๋‹จ์–ด์—์„œ ๊ณตํ†ต๋œ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ค‘ ๊ฐ€์žฅ ๊ธด ์ˆ˜์—ด์„ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
๋ฌธ์ œ ์ž์ฒด๋Š” ๊ฐ„๋‹จํ•˜์ง€๋งŒ, ์™„์ „ ํƒ์ƒ‰์„ ์ด์šฉํ•˜๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜๊ธฐ ๋•Œ๋ฌธ์— DP๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.


Solution

1
์œ„ ํ‘œ๋ฅผ ์ฐธ๊ณ ํ•ด์„œ DP ์‹์„ ์งœ์•ผ ํ•ฉ๋‹ˆ๋‹ค.
๋‘ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋งŒํผ 2์ค‘ for ๋ฌธ์„ ์ˆœํšŒํ•˜๋ฉด์„œ ๋ฌธ์ž๊ฐ€ ๊ฐ™์„ ๋•Œ์™€ ๋‹ค๋ฅผ ๋•Œ ๋‘ ์กฐ๊ฑด์œผ๋กœ dp ์‹์„ ์„ธ์›Œ์ค๋‹ˆ๋‹ค.
๋‘ ๋ฌธ์ž์—ด์ด ๊ฐ™๋‹ค๋ฉด, dp[i][j] = dp[i-1][j-1]+1
์ฆ‰, ์œ„ ํ‘œ์—์„œ ๋Œ€๊ฐ์„ ์˜ dp ๊ฐ’ + 1์ž…๋‹ˆ๋‹ค.
๋‘ ๋ฌธ์ž์—ด์ด ๋‹ค๋ฅด๋‹ค๋ฉด, dp[i][j] = max(dp[i][j-1], dp[i-1][j])
์ฆ‰, ์œ„ ํ‘œ์—์„œ์˜ ์™ผ์ชฝ์ด๋‚˜ ์œ„์ชฝ ๊ฐ’์˜ ์ตœ๋Œ“๊ฐ’์ž…๋‹ˆ๋‹ค.
๋‘ ๊ฐ’์ด ๊ฐ™์ง€ ์•Š๋‹ค๋ฉด, ๊ทธ์ „ dp ๊ฐ’ ์ค‘ ์ตœ๋Œ“๊ฐ’์ด ๋“ค์–ด๊ฐ€์•ผ ํ•˜๋Š”๋ฐ, ํ‘œ์˜ ์™ผ์ชฝ์ด๋‚˜ ์œ„์ชฝ ๊ฐ’์˜ ์ตœ๋Œ“๊ฐ’์ด ๊ทธ ๊ฐ’์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.


Description

  • ๋ฌธ์ž์—ด์€ 0๋ฒˆ ์ธ๋ฑ์Šค๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋ฏ€๋กœ, ์ด๋ฅผ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด dp ๊ฐ’์€ i์™€ j์— 1์”ฉ ๋”ํ•ด์ฃผ์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๊ทธ๋Ÿฌ๋ฏ€๋กœ ์ตœ์ข… ์ถœ๋ ฅ๊ฐ’๋„ dp[1๋ฒˆ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด-1][2๋ฒˆ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด-1]์ด ์•„๋‹Œ dp[1๋ฒˆ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด][2๋ฒˆ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด]์ž…๋‹ˆ๋‹ค.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char str1[1001], str2[1001];
int dp[1001][1001];
int main(void){
    cin >> str1 >> str2;
    for(int i=0; str1[i]!='\0'; i++){
        for(int j=0; str2[j]!='\0'; j++){
            if(str1[i]==str2[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }
            else {
                dp[i+1][j+1]= max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    cout << dp[strlen(str1)][strlen(str2)] << '\n';
    return 0;
}