작심 24/7

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 모양별로 나올 수 있는 모든 경우를 그려보고 중복되는 부분만 연산으로 저장해두려다 이렇게 푸는 게 아닌 거 같아서 검색해보니 이 4가지 도형을 회전, 대칭시킨 모든 경우가 DFS로 깊이 4만큼 탐색하는 경우와 같다는 것을 알게 되었다. (개소름) 나머지 도형 하나는 중앙 칸을 기준으로 하좌우, 상좌우, 상하우, 상하좌 로 뻗어있는 모양을 가질 수 있고 이 4가지의 경우의 수는 상하좌우를 순서 상관없이 3가지를 뽑은 경우이므로 조합으로 구해주면 된다. #inclu..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 처음에 재귀로 그냥 DFS를 구현하니까 시간 초과 걸렸었다. 중복되는 연산이 있기 때문에 DP로 최댓값을 저장해주면서 돌려야 했다. DP [i][j] = i, j에서 상 하 좌 우로 갈 때 얻는 최댓값 이라 지정하고 범위를 벗어나거나 구멍을 만나는 경우는 게임 종료 -> 어딜 더 움직일 수 없으므로 0 반환 방문했던 곳을 다시 방문하는 경우는 사이클이 생겨 무한 번 움직일 수 있는 경우이므로 -> -1을 출력하고 아예 종료 DP에 값이 있는 경우 -> 이미 최댓..

3425번: 고스택 문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 � www.acmicpc.net 구현이 귀찮았던 시뮬레이션 문제이다. 들어오는 명령어들을 저장한 후 입력 조건 중에 "명령어가 100,000개를 넘어가는 경우와 스택이 수행될 때, 1,000개 이상의 숫자를 저장하는 경우는 없다." 라는 구문이 있는데 명령어의 개수가 10만 개를 넘지 않는다는 말이었으나 '명령어 개수가 10만개를 넘어갈 때 저장되는 숫자가 1000개를 넘지 않지만 명령어의 개수는 10만개 이상일 수 있다' 라고 이해하고 최대 크기를 모르니 배열은 쓰지 못하겠다고 생각하여 각 명령..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net BFS, 완전 탐색 문제이다. 무조건 3개의 벽을 세워야 하므로 빈칸 n개 중 3개를 순서 상관없이 고르는 조합으로 구현하고 큐로 구현한 BFS로 바이러스의 개수를 구한 뒤 안전 영역의 개수 = 빈칸 개수 - 바이러스의 개수 - 3 의 최댓값을 출력해주면 된다. #include #include #include #include using namespace std; int N, M, cnt, res, x, y, tmp; int arr[8][8], dx[4] ..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 조합을 이용해서 푸는 완전 탐색 문제이다. 조합의 경우의 수를 줄이려고 입력받을 때 a, c, i, n, t를 제외시키고 중복되는 단어들도 제외시키고 배울 수 있는 단어들을 따로 만들어놓고 비교하니 시간 초과가 나왔었다. 이렇게 제외시켜서 하는 과정이 그냥 전부 비교하는 방법보다 더 오래 걸린다는 것이다. 그래서 갈아엎고 다시 짰다. 각 단어는 "a, c, i, n, t"를 무조건 포함하므로 K가 5 미만일 때는 어떤 단어도 읽을 수 없기 때문에 0을 출..

15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 문제에 나와 있는 예제인 (0, 0)에서 시작하는 0방향 0세대 드래곤 커브가 3세대까지 그려지는 과정은 끝점(1, 0)을 향해 0방향(오른쪽)을 가리키는 모양이다. 다음 세대를 위해 시작점을 가리키는 방향으로 뒤집어주면 2방향(왼쪽)을 가리키는 모양이 된다. 0세대 끝점 : (1, 0) 방향 : 2← 0세대의 끝점(1, 0)을 기준(고정)으로 시계 방향으로 90도 회전한 모양이다. 1세대의 끝점은 (1, -1)이 되고 다음 세대를 위..

14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 구현이 귀찮은 시뮬레이션 문제이다. 회전해야 하는 톱니바퀴를 먼저 체크해준 후 회전시키는 것이 포인트 네 개의 톱니바퀴를 모두 돌린다고 가정할 때 1. 시계 방향, 반시계 방향, 시계 방향, 반시계 방향 2. 반시계 방향, 시계 방향, 반시계 방향, 시계 방향 이렇게 두 가지 경우가 나온다. 이것을 이차원 배열 order에 저장해준 뒤 톱니바퀴의 번호와 방향을 입력받으면 1번 경우인지 2번 경우인지 판단해준 다음 번호에 따라서 바퀴가 돌아가는 순서대로 e..

10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net 처음엔 완전 탐색으로 풀었었는데 경우의 수가 너무 많기 때문에 당연히 시간 초과됐었다. 그래서 다른 방법들도 시도하다 안 돼서 검색해보니 Top-Down 방식으로 푸는 DP 문제였다. 문제의 나와 있는 규칙을 정리해보면 1. 왼쪽 카드의 값 > 오른쪽 카드의 값 인 경우 1) 오른쪽 카드만 버릴 수 있다 2) 왼쪽 카드만 버릴 수 있다 3) 양쪽 카드를 모두 버릴 수 있다 2. 왼쪽 카드의 값 오른쪽 카드의 값 인 경우 1) 현재 오..