어흥

문제 링크: https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 1. 주의할 점 - 언제 While문을 끝내야 하는지 알아야 한다 - 연합되는 국가를 어떻게 확인할지 알아야 한다 2. ..

문제 링크: https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력 첫째 줄에 www.acmicpc.net 1. 주의할 점 - MST에 대해 알고 있어야 한다 - Float값으로 받아들인 후, 소수점 이하 2번째 자리까지 반올..

문제 링크: https://www.acmicpc.net/problem/1963 = 1000) prime.push_back(i); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cal(); int num, start, dest; cin >> num; for (int i = 0; i > start >> dest; for (int j = 1000; j < 10000; j++) visit[j] = false; for (int j = 0; j < prime.size(); j++) visit[prime[j]] = true; queue q; visit[start] = false; in..

문제 링크: https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N TLE 발생 - 투 포인터를 이용한다(이분탐색과 원리는 얼추 비..

문제 링크: https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 1. 주의할 점 - Greedy를 이용한 방법으로 하지 말것(TC부터 답이 틀릴것이다) - Knapsack 알고리즘에 대해 알고 있어야 한다 2. 구현 - Dp[][]배열을 전부 -1로 초기화한다 - Arr[][]배열을 통해 각 물건의 무게, 가치를 저장한다 - Dp[..

문제 링크: https://www.acmicpc.net/problem/2239 2239번: 스도쿠 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중 www.acmicpc.net 1. 주의할 점 - 사전순으로 가장 빠른 답을 출력한다 - 한번 끝에 도달했으면 더 이상 구하지 않아도 된다 - 0 1 2 의..

문제 링크: https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다. www.acmicpc.net 1. 주의할 점 - MST(최소 신장 트리)를 해결하기 위해 프림 알고리즘과 크루스칼 알고리즘이 존재하는데 둘중 1개라도 알고 있어야 한다 2. 구현 - 프림 알고리즘을 적용해 문제를 해결한다 - 우선 MST를 구축하고, 1개의 마을 -> 2개의 마을로 나눈다고 했으므..

문제 링크: https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 1. 주의할 점 - 해당 칸에 도착하기 위해 바꾼 방의 최소 개수를 Check 배열에 저장한다 - 새로 방문하는 칸의 Check값을 잘 비교해야 한다 2. 구현 - BFS를 통해 문제를 해결한다 - Check배열을 전부 3000으로 초기화 한다 (50*50보다 큰 값으로 설정하면 된다) - 이동하려는 칸이 1인 경우, 이동하려는 칸의 Check값이 CV(현재까지 바꾼 방의 개수)보다 크다면 ..