체뚱로그

풀이 시간: 57m13s61(고민) + 28m16s94(참고) 시간 복잡도: O(NlogN) 공간 복잡도: O(N^2) 참고 자료: https://youtu.be/WjmEVp-Lgns?si=XVtJgDCWHFl45pv6 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 문제 풀이 문제를 분석해봤지만, 발상이 잘 떠오르지 않아서 일단 냅다 삼각형부터 만들어보았다. #include using namespace std; int N; void triangle() { int odd = 1, width = N * 2 - 1..

풀이 시간: 2h31m38s54 시간 복잡도: O(4^5 * N^2) 공간 복잡도: O(N^2) 참고 자료: https://velog.io/@statco19/boj-12100 문제 입력 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. 출력 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다. 문제 풀이 전체 코드 #include #include #include #include using namespace std; int N, ans = 0; vec..

풀이 시간: 56m24s43(문제 분석 및 정리) + 2h26m07s88(코드 작성) + 6m22s28(반례 수정) 시간 복잡도: O(N) 공간 복잡도: O(N) 문제 (문제가 길어서 생략. 맨 하단 사이트의 원문 참고) 입력 출력 문제 풀이 위와 같은 방식으로 다음처럼 구현하였다. 코드 #include #include #include using namespace std; int N, score = 0, cnt = 0; vector v; bool blue[4][6] = { false, }; // 행(4) x 열(6) bool green[6][4] = { false, }; // 행(6) x 열(4) void tile() { for (int i = 5; i >= 0; --i) { for (int j = 0;..

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