www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주�� www.acmicpc.net 각 지점의 도둑 루피를 비용으로 하여 (0,0) 지점에서 (n-1, n-1) 지점으로 가는 최소비용을 구하는 방법으로 문제를 해결했다. start지점에서도 해당 구간의 도둑루피만큼 비용이 있다. 최소비용을 구하는 방법은 다익스트라 알고리즘을 사용했다. 코드 #include #include #include #include using namespace std; int n; int board[1..

www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net vector check(11, 0); 를 이용해 a선거구와 b선거구로 나누었는데, check[1] ~ check[n]까지 1로 체크될 수 있는 모든 경우의 수를 확인해, 1로 체크된 수는 a선거구, 나머지는 b선거구로 나누었다. 이렇게 나눈 선거구가 두 선거구로 나누어질 수 있는 경우인지를 확인하고, 나누어 질 수 있는 경우일 때 두 선거구의 인구 차이를 구하는 방법을 통해 두 선거구 인구 차이의 가장 작은 값을 찾았다. 코드 #i..

www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 �� www.acmicpc.net 동전은 1,10,25,100,1000,2500... 순서이다. 그러므로 3개씩 잘라서 보면 (1,10,25), (100,1000,2500)...이다. 이 묶음들은 (1,10,25)에 뒤에 00개수의 차이이다. 그러므로 car % 100를 만드는데 필요한 1,10,25 동전의 최소 개수를 구하고, car /= 100으로 구한 금액 부분을 자르고 다시 car % 1..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net bfs를 이용하여 n에서 k까지 가는 가장 빠른 시간을 구하고, int from[100001];을 이용해 해당 지점으로 올때 어떤 지점에서 왔는지 저장해서 경로를 구한다. 코드 #include #include #include using namespace std; int discovered[100001]; int depth[100001]; int from[100001]; /..

www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 모든 국가를 여행하기 위해 타야 되는 비행기 종류의 최소 개수는 최소 스패닝 트리의 간선의 개수이므로 n-1이다. 코드 #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int tc; int n, m; int a, b; cin >> tc; for..

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적�� www.acmicpc.net multiset을 이용하여 이중 우선순위 큐를 표현했다 코드 #include #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int tc; int k; string command; int n; multiset q; //multiset을 이용하여 이중 우선순위..