문제 이해 단계 https://www.acmicpc.net/problem/1238 N개의 마을에 연결된 M개의 단방향 도로가 존재한다. 각 도로에는 오고 가는 시간(비용)이 존재한다. N개의 마을 중 특정 마을 X로 왕복해야 하는데, 어느 마을에서 출발하는 것이 가장 시간이 오래 걸리는가? 그때의 소요 시간을 구하는 출력하는 문제 문제 접근 단계 문제 유형 유추 N개의 마을에 연결된 M개의 단방향 도로라는 말을 읽자마자 바로 그래프 탐색이 떠올랐다. 마을을 정점으로 치환하고, 단방향 도로를 단방향 간선으로 본다. 그리고 걸리는 시간을 각 간선의 가중치로 보면 완벽한 그래프 탐색 문제이다. 로직 어쨌든 이 학생들은 무조건 최단 거리로 오고 간다고 했다. 그래프 탐색에서 최단거리라고 하면 생각나는 것이 크루..

문제 이해 단계 https://www.acmicpc.net/problem/13905 섬 위에 N개의 집과 M개의 다리가 존재한다. 그리고 각 다리에는 무게 제한 K가 걸려있다. 입력으로 출발지와 목적지가 주어지는데, 혜빈이는 최대한 많은 금빼빼로를 들고 목적지까지 도착해야 한다. 각 다리에서 무게제한까지만 빼빼로를 들 수 있을 때 최대 몇 개까지 빼빼로를 옮길 수 있는가? 문제 접근 단계 제한사항부터 살펴보자. 존재하는 집의 수(N)는 100,000개, 다리의 수(M)는 300,000이다. 최대 10^5 * 10^5 = 10^10이므로, 완전탐색으로 하면 시간초과가 뜬다. 따라서 하나하나 비교하는 것은 안되고, 다른 방법이 필요하다. 그래프 탐색 결국엔 집과 집을 연결하는 것이 다리고, 그 다리에는 무게..

문제 이해 단계 https://www.acmicpc.net/problem/21941 소문자 문장 S가 주어지고, 문자열 리스트들이 주어진다. 각 문자열 리스트들은 각자 점수를 가지고 있다. 문장 S에서 모든 문자들을 지워야 하는데 아래 2가지 연산만 할 수 있다. 1. 문자열 리스트에 존재한다면 해당 부분을 지우고, 그 문자열만큼의 점수를 얻는다. 2. 문자 하나를 지우고 1점을 얻는다. 해당 연산을 통해 모든 문자를 지울 때, 얻을 수 있는 최댓값을 구하는 문제 문제 접근 단계 범위 파악 문제 조건부터 살펴보자. 문장 S는 최대 1000개까지, 문자열 리스트는 100개, 그리고 점수는 개당 10,000점까지 가능하다. 만약 문장의 길이가 1000이고, 문자열이 하나로 구성된, 개당 10,000점짜리가 ..

문제 이해 단계 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net NxN 크기의 맵에 M개의 바이러스를 놓으려고 한다. 바이러스는 맵에 ' 2 '라고 표시되어 있는 곳에 밖에 놓지 못한다. 바이러스는 1초당 상하좌우로 인접한 모든 빈칸(1이라고 적힌 칸을 제외)한 칸으로 퍼진다. M개의 바이러스를 배치하여 최소한의 시간으로 모든 맵에 바이러스를 퍼뜨릴 때, 이 최소 시간은? 만약 모든 맵에 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다. 문제 접근 단계 문..

문제 이해 단계 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net N명이 학생이 있고 그 학생들 사이에 M개의 친구 관계가 존재한다. 그리고 각각의 학생마다 친구비가 존재하는데, 친구 관계인 친구였다면 그중 하나에게만 지불하면 된다. 해당 조건으로 K원을 가지고 있을 때, N명 학생과 모두 친구를 맺을 수 있는 최소 비용을 구하시오. 만약 구할 수 없으면 "Oh no"를 출력한다..

문제 이해 단계 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net n개의 정점과 m개의 간선이 존재한다. 그리고 간선 사이에는 가중치가 존재한다. 모든 정점에서 다른 정점으로의 경로표를 만들어야 한다. 한 정점에서 다른 정점으로 최단경로로 움직일 때, 거쳐야 하는 다른 정점을 경로표에 적어 넣는다. 그리고 경로표 전체를 출력하는 것이 해당 문제이다. 문제 접근 단계 로직 유추 문제를 보면 바로 정점과 간선이 있는 그래프를 준다. 이 점을 보니 바로 그래프..

문제 이해 단계 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net MxN짜리 맵에 입력으로 출발 좌표와 목적 좌표가 주어진다. 출발지에서 로봇이 출발하는데 로봇이 할 수 있는 행동은 아래의 2가지이다. 명령 1. Go k : k는 1,2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸만큼 움직인다. 명령 2. Turn dir : dir은 left 또는 right이며, 각각 왼쪽 또는 오른쪽으로 90도 회전한다. 로봇을 목적지에 도착시키고, 원하는 방향..

문제 이해 단계 https://www.acmicpc.net/problem/16432 호랑이에게 N일 동안 떡을 줘야 한다. 떡을 줄 때 이틀 연속해서 같은 번호의 떡을 주어선 안된다. 떡의 종류는 1~9번까지 총 9개가 존재한다. 입력으로 N일이 들어오고, 그다음 줄부터 i번째 날의 가져갈 떡의 수 m과 떡의 종류가 주어진다. 호랑이에게 떡을 줄 수 있는 경우엔 여러 가지 경우의 수 중 하나를 출력하고, 그렇지 않은 경우엔 -1을 출력한다. 문제 접근 단계 제한사항부터 살펴보면, N(일)의 최대는 1,000이다. 떡의 종류는 최대 9개까지 가능하다. 아이디어 처음에는 당연히 연속되는 경우를 제외하고, 모든 종류를 하나씩 살펴보는 백트래킹 방식을 사용하려고 했는데 이 방식은 8^1,000이 되기 때문에 시..