BOJ 문제풀이 1

1182 부분수열의 합

N이 최대 20입니다 비트마스킹을 이용하여 가능한 모든 부분수열의 합을 본다 하더라도 $O\left ( N2^N \right )$입니다

 

20502 Gum색

게시글을 우선순위 순서대로 방문하면서 해당 게시글에 키워드가 있는지 확인하면 $O\left ( QNM \right )$해결 할 수 있습니다

 

1012 유기농 배추

Board[i][j]가 1이면서 아직 방문하지 않은곳을 시작으로 DFS를 돌면서 총 몇번 DFS가 호출되었는지 카운팅하면 됩니다

 

1463 1로 만들기

3가지 연산에 대해 dp를 돌려주면 해결 할 수 있습니다

다만 N이 100만이라 $O\left ( N \right )$안에 해결하기 위해 저는 bottom-up으로 풀었습니다

 

1915 가장 큰 정사각형

dp문제입니다

dp[i][j] := i,j를 오른쪽 하단으로하는 정 사각형의 변의 길이

dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 입니다

물론 이때 i,j가 0이면 그냥 0입니다

상단과 좌변을 먼저 초기화해주고 dp를 채워주면 해결 가능합니다

가장 큰 정사각형

붉은색으로 표시된곳이 i,j입니다

붉은색으로 표시된 사각형을 오른쪽 하단에 포함하는 가장 큰 정사각형의 크기는 1,2,3번을 오른쪽 하단에 포함하는 가장 큰 정사각형 중 가장 작은 것에 +1을 해주면 됩니다