일단 메모장에 적은거 써봄.

사용한알고리즘 : Dynamic Programming ( 동적 계획법 )


풀이


1. 아이디어

일단 각 위치에서 상하좌우로 이동할때 일정한 조건을 만족하며 최소 비용으로 이동하는 경로를 찾음.

DP를 사용해서 각 위치에서 최소 비용을 계산하고 저장함.


2. 접근 방법:

dp 배열을 사용해서 각위치에서의 최소비용을 저장함.

dp[i][j]는 i번째 위치에서 j 상태일때의 최소비용을 의미함.

여기서 j는상태를 나타내며 각 비트는 다음과 같이 나타남.

0: 현재 위치에 아무 것도 놓이지 않음

1: 현재 위치에 블록이 한 개 놓임

2: 현재 위치에 블록이 두 개 놓임

3: 다음 위치에 블록이 두 개 놓임

재귀적으로 각 위치에서의 최소 비용을 계산함.

재귀 함수 sv는 현재 위치와 상태를 인자로 받고 현재 위치부터 마지막 위치까지의 최소비용을 반환함.


3. 점화식

현재 위치에서 갈수있는 다음 위치와 상태를 확인하고 각 경우의 최소 비용을 계산함.

최소 비용은 현재 위치에서 블록을 추가하는 경우와 추가하지 않는 경우에서 작은 값을 선택함.


4. 주의점

초기화가 중요함. dp 배열은 메모이제이션을 위해 -1로 초기화됨.

각 위치에서의 상태를 나타내는 비트 마스크를 사용하여

상태를 효율적으로 표현함


시간 복잡도


전체 코드의 시간복잡도는 대략적으로 O(T*N)임.