체뚱로그

풀이 시간: 57m36s00 시간 복잡도: O(NM) 공간 복잡도: O(NM) 문제 입력 출력 문제 풀이 본 문제는 단순 시뮬레이션 구현 문제이다. 문제 자체에 조건들이 아주 친절하게 설명이 되어있기 때문에 해당 조건들을 하나씩 따라가면서 풀다보면 쉽게 구현할 수 있는 문제이다. 전체 코드는 다음과 같다. 자세한 설명은 주석으로 대체한다. 전체 코드 #include using namespace std; int N, M, r, c, d, cnt = 0; int arr[51][51] = { 0, }; int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // dir[i][j] : 북 동 남 서, i번째 줄, j번째 칸 void cleanRoom(int r, int c)..

풀이 시간: 1h42m11s75(초반 삽질) + 3h05m13s35 시간 복잡도: O(N^2 * log N) // log N은 우선순위 큐의 삽입 및 삭제 연산의 시간 복잡도 공간 복잡도: O(N^2) 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, ..

풀이 시간: 1h04m15s54 시간 복잡도: O(NM) 공간 복잡도: O(NM) 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오...