목록PS/BOJ (74)
체뚱로그
풀이 시간: 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초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, ..
풀이 시간: 1h04m15s54 시간 복잡도: O(NM) 공간 복잡도: O(NM) 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오...
풀이 시간: 2h33m58s30 + 1h 시간 복잡도: O(4^10) 공간 복잡도: O(10^4) 참고 자료: https://junbastick.tistory.com/37 문제 시리즈 https://www.acmicpc.net/problem/13459 https://www.acmicpc.net/problem/15644 https://www.acmicpc.net/problem/15653 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두..
풀이 시간: 3h25m51s34 시간 복잡도: O(G*S + 101^2) // G: 총 세대 수, S: 각 세대별 생성 좌표 수, check() 함수 이중 반복문 공간 복잡도: O(101^2) 문제 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때,..