목록2024/03/27 (3)
체뚱로그
풀이 시간: 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지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) ..