CEO

문제 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 풀이 문제를 풀기 위해서는 위상 정렬에 대한 이해가 필요하다. 이에 대한 개념을 이해하였다면 위상 정렬을 그대로 구현한 후, 다음 조건을 이해하면 쉽게 답을 찾을 수 있다. 위상 정렬을 이용하면 탐색 순서는 1, 4, 6, 2, 3, 5이다. 1, 4, 6 과목은 선수 과목(진입 차수가 0)이 없다. 선수 과목이 없는 경우이므로 1학기에 수강할 수 있다. 2, 3의 경우 진입 차수가 1이고, 선수 과목은 1이다. 선수 과목이 있으므로 1번 과목을 수강한 이후에 수강할 수 있다. ..

문제 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 문제 풀이 완전 탐색 + dp 문제이다. 탐색한 경로를 다시 탐색하지 않기 위해서는 메모이제이션을 통해, 각 공간을 지날 때 최솟값을 기록하고 이전의 값을 사용하는 방식을 사용하면 된다. 재귀로 풀면 문제는 어렵지 않게 풀 수 있으며 점화식은 다음과 같다. `dp[r][c][cur_dir] = min(dp[r][c][cur_dir], recursive_find(next_r, next_c), next_dir) + boar..

문제 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 풀이 적어도 유치해야 하는 고객 수 C명과 도시의 개수 N이 주어진다. 이때 각 도시에는 홍보비용과 그 비용으로 유치할 수 있는 고객에 대한 정보가 제공된다. 이때, 최소 비용으로 적어도 C명의 고객의 수를 유치하는 경우를 반환하는 문제이다. 문제를 풀기 위해서는 메모이제이션을 통해, 다음과 같이 점화식을 세우면 해결할 수 있다. `dp[N명의 고객을 유치하는데 드는 비용] = min(dp[N명의 고객을 유치하는데 드는 비용], dp[N명의 고객을..

문제 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 풀이 입력값으로 파이어볼의 위치 (r, c), 질량(m), 방향(d), 속력(s)이 주어진다. 시뮬레이션 문제이므로 다음과 같은 과정을 순차적으로 진행한다. 모든 파이어볼은 자신의 방향으로 속력만큼 이동한다. 이동을 마친 후, 이동된 파이어볼들이 같은 칸에 2개 이상 있다면 다음과 같이 처리한다. 파이어볼은 4개로 나누어진다. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다. 질량은 `합쳐진 파이어볼 질량의 ..

문제 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 풀이 문제에서 격자판과 궁수의 공격 거리 제한 D가 주어 질 때 제거할 수 있는 적의 최대 수를 출력하는 문제이다. 궁수는 3명을 배치할 수 있으며, 배치 가능한 범위는 열의 범위인 M까지 이다. 궁수의 경우 3명만 배치 가능하므로 각 좌표에 대해 조합(Combination)으로 경우의 수를 구해 후보군을 구한다. 후보군을 구하였다면 후보군을 모두 순회하면서 공격 가능한 거리에 따라 적을 제거하고 적이 앞으로 움직이는 과정을 반복하여 제거한 적의 수를 비교하여 최..

문제 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 문제 풀이 목표가 되는 문자열과 일치하는 경우의 수를 찾는 문제이다. 이를 위해서 `상, 하, 좌, 우`로 K 만큼씩 이동할 수 있다. 문제를 풀기 위해서는 단순히 DFS를 통해 경우의 수를 찾게 되면 시간 초과가 발생한다. 따라서 메모이제이션을 통해 이미 체크한 경우의 수라면 해당 경우의 수를 체크하지 않아야(가지치기) 한다. 처음에는 `dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))`를 사..

문제 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제 풀이 5 x 5 크기의 토네이도가 방향을 전환하며, 현재 있는 모래에 영향을 미치는 문제이다. 문제를 풀기 위해서는 `상, 하, 좌, 우`로 전환되는 경우의 토네이도에 대해 사전에 초기화가 필요하다. tornado = [ (None, None, 2, None, None), (None, 10, 7, 1, None), (5, 'a', None, None, None), (None, 10, 7, 1, None), (None, N..

문제 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 문제에서 배열 A가 주어지면, 배열의 행, 열의 수에 따라 정렬을 수행 후 행렬에 값을 추가한다. 조건은 다음과 같다. 행의 개수가 열의 개수보다 크거나 같은 경우 배열 A의 모든 행에 대해 정렬을 수행한다 행의 개수가 열의 개수보다 작은 경우 배열 A의 모든 열에 대해 정렬을 수행한다. 정렬을 위해서는 한 행 또는 한 열의 수와 등장 횟수를 기준으로 정렬한다. (count, number)와 같은 기준으로 정렬한다. 정렬할 때, 0은 ..