목록PS (77)
체뚱로그
풀이 시간: 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 미만의 자연수이다. 출력 첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다. 문제 풀이 주사위를 굴릴 때마다 전개도를 어떻게 저장할 것인가? 현재 이동 방향을 따로 저장해준 후, 위 전개도대로 각 위치를 변경해주면 된다. 따라서 나는 이동 방향과 주사위 각 방향에 대한 값을 따로 저장해두기로 했다. 우선 동남서북 순서대..
풀이 시간: 2h08m57s01 시간 복잡도: O(NMRC) 공간 복잡도: O(NM + RC) 문제 입력 첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다. 먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다. 다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은..
풀이 시간: 56m01s01(분석) + 1h07m13s92(초기 코드) + 1h01m41s46(오류 수정) 시간 복잡도: O(N) 공간 복잡도: O(N) 문제 입력 첫째 줄에 N, K가 주어진다. 둘째 줄에는 A1, A2, ..., A2N이 주어진다. 출력 몇 번째 단계가 진행 중일때 종료되었는지 출력한다. 문제 풀이 처음에 이 문제를 읽고 20분동안 분석해보았는데, 조금 헷갈리는 부분이 있어 질문 게시판을 참고하여 문제를 좀 더 잘 풀어서 설명해준 글들을 읽고 다시 분석했다. https://www.acmicpc.net/board/view/116253 https://www.acmicpc.net/board/view/114048 헷갈리는 내용 정리 ▪️ 출력에서 말하는 '단계'라는 것은 지문에 나온 1~4번..