목록2024/04/14 (2)
체뚱로그
풀이 시간: 52m20s45 시간 복잡도: O(K) 공간 복잡도: O(1) 문제 입력 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다. 출력 총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한..
풀이 시간: 1h13m42s48(문제풀기) + 14m20s69(반례수정) 시간 복잡도: O((4^C)NM) 공간 복잡도: O(NM) 문제 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지대의 최소 크기를 출력한다. 문제 풀이 1. CCTV 위치 전부 저장 2. CCTV를 전부 돌면서 깊이 우선 탐색(dfs) 진행 (dfs 재귀호출 -> CCTV 순차적으로 진행) 3. 이때 한 CCTV마다 모든 방향을 탐색해야하므로 백트래킹 (arr을 이전 ..