작심 24/7

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 완전 탐색, DP 두 가지 방법으로 풀 수 있다. 완전 탐색은 1일부터 차근차근 가능한 날을 모두 골라 최댓값을 구해주면 되고 DP는 i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 최대 이익, i 일을 선택하지 않을 때 얻는 최대 이익) → i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 이익 + i+T[i]일에 얻는 최대 이익, i+1일에 얻는 최대 이익) → DP[i] = max(P[i] + DP[i + T[i]], DP[i + 1]) 라는 점화식을 세워주고 재귀로 구현하면 된다. 1. 완전 탐색 #include #include using namespace std; int N, M..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 선거구로 나눌 때 각 선거구 안에 있는 영역들은 모두 연결되어 있는 상태여야 한다. 그러므로 두 선거구로 나눌 수 없는 경우는 연결되어 있는 그룹이 세 개 이상일 때이므로 이 경우를 가려주기 위해 먼저 BFS로 연결된 그룹이 몇 개인지 세어준다. 3개 이상일 경우 -> -1 출력 2개일 경우 -> 두 그룹이 각각 선거구이므로 이때 인구의 차 출력 1개일 경우 -> 모두 연결된 상태이므로 다음 단계 넘어감 두 선거구로 나누는 방법은 N개 중에서 K개를 순서 상관없이 뽑는 조합으로 구..

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에 값이 있는 경우 -> 이미 최댓..

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을 출..

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

14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 단순한 DFS 문제인 줄 알고 대충 읽고 짜다가 갈아엎었다. 시뮬레이션 문제이므로 작동 순서를 잘 읽고 구현해야 한다. 1. 현재 방향에서 왼쪽 방향으로 일단 회전하고 그 방향의 공간이 비어있는지 확인한다. 2. 청소하지 않은 빈 공간이라면 -> 전진한다. (재귀) 벽이거나 청소를 한 공간이라면 -> 왼쪽 방향으로 한 번 더 회전한다. 3. 왼쪽 방향으로 총 네 번 회전하며 확인했는데도 빈 공간이 없을 경우 현재 방향은 그대로 뒤로 후진한다. 4. 후진할 공간이..

1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 탐욕법으로 가장 큰 큐브부터 박스에 넣어본 후 남은 부분들을 세 가지로 나누어 재귀로 계속 반복한다. 그림과 같이 현재 가장 큰 큐브 l, w, h를 제외하고 남은 1번, 2번, 3번 상자들은 각각 다시 하나의 상자로 생각하여 현재 가장 큰 큐브를 제외하고 남은 세 가지 상자들을 다시 각각 하나의 상자로 생각하고 ... 이 과정을 가로, 세로, 높이 중 하나라도 0이 될 때까지 계속 반복한 후 빠져나와서 카운트를 출력한다. 가로..