어흥

문제 링크: 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(현재까지 바꾼 방의 개수)보다 크다면 ..

문제 링크: https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다. www.acmicpc.net 1. 주의할 점 - 처음에 비숍을 안넣는게 최선일 수 있다 - 체스판과 관련된 문제는 흑백으로 나눠서 생각하도록 한다 -> 시간복잡도가 줄어든다 2. 구현 - 백색 칸과 흑색 칸을 구분해서 흑색칸일 때 최대 + 백색칸일 때 최대를 구한다 - 해당칸이 비숍을 놓을 수 있는 칸인 ..

문제 링크: https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자. 격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자 www.acmicpc.net 1. 주의할 점 - 이동할 때, 범위를 벗어나지 않도록 한다 - 이동할 때, 다음 위치가 1이면 가지않는다 - 이미..