체뚱로그

풀이 시간: 1h23m18s29 + 1h20m44s32 + 42m34s25시간 복잡도: O(NMH) // H: 집의 개수공간 복잡도: O(N^2)참고 자료: https://yabmoons.tistory.com/50문제입력첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.출력첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.문제 풀이초기 고민..

풀이 시간: 2h12m17s71시간 복잡도: O(N^2*L)공간 복잡도: O(N^2)문제입력첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.출력첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.문제 풀이전체 코드#include #include #include using namespace std;int N, L, ans = 0;vector cnt1, cnt2;int arr1[101][101] = { 0, };int arr2[101][101] = { 0, };vector isRoad(int arr[][101]) { vector cnt(N, true); // 각각의 길을 지나갈 수 있는..

풀이 시간: 2h30m33s56(문제풀이) + 2h13m41s24(틀린 부분 찾기)시간 복잡도: O(N^2)공간 복잡도: O(N^2)문제입력첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.출력격자의 밖으로 나간 모래의 양을 출력한다. 문제 풀이헷갈리는 조건 정리1. α 위치는 현재 진행하는 y방향의 그 다음 방향이다. α = ( cR + dir[cDir][0], cC + dir[cDir][1] )2. 토네이도가 이동할 때 현재 위치(x), 다음 위치(y) 값의 변화는 없다.3. α에는 각 위치에서의 비율만큼의 값을 뺀 값이다. 그냥 α 값에다가 현재 위치 값의 55%를 하면 안된다. 소숫점 ..

풀이 시간: 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을 이전 ..

풀이 시간: 2h20m20s95 시간 복잡도: O(KNM) 공간 복잡도: O(NM) 문제 입력 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (2 ≤ N, M ≤ 20), 그리고 이동하는 횟수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수이다. 출력 첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다. 문제 풀이 주사위를 굴릴 때마다 전개도를 어떻게 저장할 것인가? 현재 이동 방향을 따로 저장해준 후, 위 전개도대로 각 위치를 변경해주면 된다. 따라서 나는 이동 방향과 주사위 각 방향에 대한 값을 따로 저장해두기로 했다. 우선 동남서북 순서대..