1~N번까지의 헛간 중 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며 하나의 통로는 두 헛간을 연결합니다. 전체 맵에서 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다. 1번헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다....
화성 탐사 ACM-ICPC 최단거리
화성 탐사 기계는 에너지를 효율적으로 사용하기 위해 최적의 경로를 찾아야 합니다. 기계가 존재하는 공간은 NxN 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용이 존재합니다. 가장 왼쪽 위 칸인 [0][0]위치에서 가장 오른쪽 아래 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하세요 이동가능한 방향은 상하좌우 인접한방향입니다....
정확한 순위 K대회 최단거리
시험을 본 학생 N명의 성적을 분실하고 성적을 비교한 결과 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다른데, 당므은 6명의 학생에 대하여 6번만 성적을 비교한 결과입니다. 이를 유추해서 순위를 정확히 알 수있는 학생도 있고 알수 없는 학생도 있습니다. 순위를 정확히 알 수 있는 학생은 모두 몇명인가요? 해당 문제도 결국 최단 경...
플로이드 백준 11404번 최단경로
https://www.acmicpc.net/problem/11404 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 ...
편집 거리 골드만삭스 DP
두 개의 문자열 A와 B가 주어졌을때 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할때는 다음의 세 연산 중에서 한번에 하나씩 선택할 수 있습니다. 삽입 : 특정한 위치에 문자를 삽입합니다. 삭제 : 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체 : 특정한 위치에 있는 하나의 문자를 다른 ...
병사 배치하기 백준 18353번 DP
https://www.acmicpc.net/problem/18353 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고...
못생긴 수 구글 인터뷰 DP
못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2,3,5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴수라고 가정합시다. 따라서 못생긴 수들은 1,2,3,4,5,6,8,9,10,12,15 순으로 이어지게 됩니다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하세요 예를 들어 11번째 못생긴 수는 15입니다....
퇴사 백준 14501번 DP
https://www.acmicpc.net/problem/14501 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각...