기본 콘텐츠로 건너뛰기

9252 : LCS2(미제) (Dynamic Programming) [C,C++]

처음 접근은 LCS1 문제를 응용해 

2차원 배열에 각 인덱스마다 문자열을 만들고 하나씩 늘려가는 식으로 접근을 하였다.

하지만 이렇게 풀다보니 메모리 초과가 뜨는 것이었다.

어떻게 풀지 고민하다가..

완성된 LCS의 배열에 맨 끝부터 처음까지 행마다 검색을 하여 위의 값과 같다면 위로

더이상 없다면 그 행의 알파벳을 입력하고 왼쪽 대각선으로 이동하는 반복문을

사용했는데.. 이게 틀렸다고 나온다. 시간적으로나 공간적으로나 맞는 것 같은데.. 

반례도 다 검색해봤지만 모두 맞게 나와서 내일 다시 풀어봐야겠다..



라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }
댓글 쓰기
자세한 내용 보기

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE
댓글 쓰기
자세한 내용 보기

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기