체뚱로그

풀이 시간: 2h30m35s08(초기 코드) + 48m12s57 시간 복잡도: O(RCT) 공간 복잡도: O(RC) 참고 자료: https://yabmoons.tistory.com/238 문제 입력 첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다. 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다. 출력 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다. 문제 풀이 초기 코드 #include using namespace std; int R, C,..

풀이 시간: 2h19m12s02 시간 복잡도: O(N^2) 공간 복잡도: O(N^2) 참고 자료 https://hyeo-noo.tistory.com/137 https://yabmoons.tistory.com/592 문제 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다. 출력 첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다. 문제 풀이 원래도 DP는 잘 못풀었지만..

풀이 시간: 3h02m13s13 시간 복잡도: O((n + m) * log n) 공간 복잡도: O(n + m) 참고 자료 https://www.acmicpc.net/board/view/117492 https://devmath.tistory.com/69 유사 문제 https://www.acmicpc.net/problem/1504 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) ..

풀이 시간: 44m33s83 시간 복잡도: O(N) 공간 복잡도: O(N) 참고 자료: https://bbeomgeun.tistory.com/18 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 ..

풀이 시간: 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초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, ..