영화 수집 문제 쿼리마다 i 번째 영화 위에 쌓여있는 다른 영화의 수를 출력하는 문제이다. 문제 풀이 naive하게 쿼리마다 현재 영화보다 위에 있는 영화를 카운트하는 방식으로는 \(O(NM)\) 이라 불가능하고, 힌트로는 영화를 꺼냈을 때 그 부분이 밀쳐지지 않고 비워진다는 방식으로 이해한다는 것이다. 그리고 영화를 꺼내면 맨 위에 차곡차곡 쌓는다. 그래서 현재 i층에 영화가 존재하는지, 안 하는지를 저장하는 \(check[i]\)을 생각해 보자. index value 0 0 1 0 2 0 .... .. m 1 m+1 1 m+2 1 ... ... m+n-1 1 초기의 \(check[i]\)값은 위와 같다. 여기에 현재 i번째 영화가 어디 있는지에 대한 \(idx[i]\) 배열을 만들어 준다. 초기에는 ..
소문난 칠공주 문제 상하좌우로 연결된 크기가 7이고 S가 4 이상 포함된 컴포넌트의 개수를 세는 문제이다.개 문제 풀이 한 점을 기준으로 단순 bfs나 dfs로는 십자가 모양 등을 찾을 수가 없다. 따라서 25개의 학생 중에서 7명을 뽑고 여기서 S가 4 이상 포함되었는지 그리고 모두 연결되었는지를 판단하는 방식으로 구현하였다. \( \begin{pmatrix} 25 \\ 7 \end{pmatrix} = 480,700\) 이고 7명 중 한 명에서 dfs로 최대 컴포넌트 크기가 7인 경우만 가능한 경우로 판단하여 정답을 구하면 된다. \( O(480,700*25) \) 로 해결 가능하다. 소스 코드
운전 면허 시험 문제 (1,1)에서 (M,N)까지 이동하는데 남쪽과 동쪽으로만 이동할 수 있고 위 그림과 같이 이동하는데 길 상태에 따라 연료 g가 소모된다. 방향을 틀 때 1의 시간이 소모되고, 1개 변을 이동할 때 l 시간이 소모될 때 최대 가용 연료 G 이내로 들어올 수 있는 최소 시간을 구하는 문제이다. 문제 풀이 가장 쉽게 떠올릴 수 있는 풀이는 \(O(NMG)\) bfs 서칭 하는 방법이다. 물론 공간, 시간복잡도가 불가능한 풀이이고, 핵심적인 힌트는 이동하는데 걸리는 시간은 이동이 남쪽과 동쪽만 가능하므로 변의 개수는 의미가 없고 방향을 바꾼 횟수만 카운트해주면 된다는 점이다. 따라서 dp 테이블을 \(dp[x][y][k][dir]=(1,1)에서\: (x,y)좌표까지\: k번\: 방향을\: ..