🔗문제 보러가기 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🧑‍💻풀이 과정 동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다. 진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다. *constructionTimes[i] : i 번째 건물의 건설 시간 *answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간 answers[o..

🔗문제 보러가기 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 🧑‍💻풀이 과정 위상 정렬(Topological Sort)에 대해 공부한 후, 풀어보려고 골랐던 문제 중 하나입니다. 위상 정렬 알고리즘을 그대로 적용하되, 쉬운 문제부터 풀어야 하니 우선순위 큐(Priority Queue)를 대신 사용해주면 끝인 문제입니다. 이 외에는 더 이상 설명할 내용이 진짜로 없기에, 아래에 코드를 첨부하도록 하겠습니다. ✏️소스 코드 및 결과 #include #include #include..

🔗문제 보러가기 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 👨‍💻풀이 과정 처음에 문제를 보고 별 생각없이 배열 선언하고 분할 정복을 했다가 메모리 초과. ($2^{15}\times 2^{15}$) 배열 없이 카운팅 변수 하나로만 아무 생각없이 셌다가 시간 초과. (하나씩 돌면서 점검하면 결국 $\mathrm{O}(2^{15}\times 2^{15})$) 그래서 4등분을 하고, 찾고자 하는 (행, 열)이 해당 칸에 없는 경우에는 사각형 개수만큼 더해 주었습니다. 만약 찾고자 하는..

🔗문제 보러가기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🧑‍💻풀이 과정 얼마 전에 다익스트라 알고리즘(Dijkstra Algorithm)을 공부했었으니, 머릿 속에서 인출하는 연습을 위해 비슷한 유형의 문제를 하나 풀어봤습니다. 우리 말이 어려운 건지, 제가 멍청한 건지 모르겠지만 매번 헷갈리는 것 같아요... 그래서 연습장에 그림 그려가며 풉니다. ( "distances[v] vs distances[u] + nextCost" 👉🏻 이게 젤 헷갈립니다. ) 알고리즘은..

🔗문제 보러가기 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 🧑‍💻풀이 과정 DFS + 백트래킹으로 풀 수 있는 문제입니다. 처음에는 같은 문자 방문 여부를 위해 set을 이용했는데, 시간 초과가 나더라구요. 그래서 시간을 줄이기 위해 다른 방법을 생각했는데, 알파벳은 26개가 있고 각각 한 번씩만 방문할 수 있으니, vector Alphabet(26, false) 배열을 통해 방문 여부를 관리하니 통과가 되었습니다. $\mathrm{O}(1)$ 과 \( \mathrm{O(log \ N)..

🔗문제 보러가기 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🧑‍💻풀이 과정 연구소의 크기가 최대 $8\times 8$ 이기 때문에 벽을 3개 설치하는 모든 경우의 수에 대해 탐색하여 풀었습니다. 백트래킹과 BFS 탐색을 잘 구현하는 것이 목표인 문제인 것 같네요. 2차원 배열에 연구소 정보를 입력 받고, 바이러스의 위치 정보도 별도의 배열에 저장한다. 조합(Combination) 방식을 이용해 열 방향 순서로 벽 3개를 설치한다. 빈 공간일 때에만 벽을 설치한다. 벽을 3개 설치 다 했다면, 3번 과정을 진행 후..