1일1알

dp테이블을 이용해서 bottom-up 방식으로 해결할 수 있는 문제이다. 주의해야 할 점은 문제의 조건에서 비용의 제곱이 1000000보다 작다고 했기 때문에 음수가 비용으로 들어올 수도 있다는 점이다. 그렇기 때문에 들어오는 모든 경우들을 확인해주어야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int cn..

맨 앞의 전구부터 순차적으로 만약 자기보다 앞에 있는 전구가 목표로 하는 상태와 같으면 누르지 않고 다음 전구로 넘어가고, 만약 다르다면 스위치를 눌러서 상태를 같게 만들어준 뒤 다음 전구로 넘어가는 방식으로 문제를 해결하였다. 여기서 주의해야할 점은 맨 앞의 전구는 자기보다 앞에 있는 전구가 없어서 비교가 불가능하기 때문에 맨 앞에 있는 전구를 눌렀을 때와 안눌렀을 때 이 두 경우를 모두 조사해야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; st..

백트래킹을 이용하여 빈 칸에 3개의 장애물을 놓는 모든 경우를 만들고 각각의 경우마다 배열을 검사하면서 하나의 경우라도 선생님의 감시를 피할 수 있다면 YES, 하나도 피할 수 없다면 NO를 출력하도록 구현하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; char arr[6][6]; bool isPossible = false; int posR[4] = { -1,0,1,0 }; int posC[4] = { 0,1,0,-1 }; bool IsMeet() ..

간단한 bfs 응용문제이다. 코드에 전혀 문제가 없는데 통과가 안돼서 계속 고민하다가 문제를 다시 읽어봤는데 가로와 세로를 거꾸로 입력받았었다. 역시 문제는 꼼꼼히 읽어야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; int posR[4] = { -1,0,1,0 }; int posC[4] = { 0,1,0,-1 }; int bfs(char c, int row, int col, const vector &v, vector &visited) { qu..

대각선까지 고려하는 bfs, dfs 탐색 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int m, n; cin >> m >> n; int posR[8] = { -1,-1,0,1,1,1,0,-1 }; int posC[8] = { 0,1,1,1,0,-1,-1,-1 }; vector v(m, vector(n)); for (i..

간단한 dp문제일 줄 알았는데, 중복을 허용하지 않는다는 조건이 있어서 풀이를 생각하는데 시간이 조금 걸렸다. 생각해낸 해결법은 오름차순으로 정렬된 경우만 고려하는 것이다. 2차원 dp테이블을 만들어서 dp[i][j]는 i를 만드는 데 마지막에 사용한 숫자는 j 이라는 정보를 저장해서 문제를 해결하였다. dp[4][1]은 4를 만드는데 마지막에 1이 사용되고, 오름차순으로 정렬된 경우만 고려하므로 3을 만들 때 마지막에 1이 사용된 경우만 가능하다. 그러므로 dp[4][1]=dp[3][1] 이기 때문에 dp[i][1]=dp[i-1][1] 이라는 점화식을 하나 얻을 수 있다. dp[4][2]는 4를 만드는데 마지막에 2가 사용되고, 오름차순으로 정렬된 경우만 고려하기 때문에 2를 만들 때 마지막에 1이 사..