#문제 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #접근방법 이 문제는 지도의 크기가 최대 8*8 = 64칸이 최대이므로 모든 경우의 수를 구해도 64*63*62*dfs가 걸리는 시간이므로 시간안에 돌아간다. 벽 3개를 설치하는 모든 경우의 수에서 dfs를 돌려서 안전영역이 최대가 되는 경우를 계산해주면 된다. #풀이 #include int arr[10][10]; int arr2[10][10]; int virus[64][2]; i..
#문제13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #접근방법이 문제는 숨바꼭질 2에서 변형된 문제이다. https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-12851%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-2-CC [백준] 12851번 : 숨바꼭질 2 [C/C++]#문제 12851번: 숨바꼭질 2 h..
#문제 13172번: Σ https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net #접근방법 이 문제를 처음 봤을 때 글이 너무 많고, 또 이해하기가 힘들었다. 두 세번정도 읽으니 전체적인 맥락과 수식들이 눈에 보여서 이해가 되었다. 페르마 소정리와 모듈러 역원에 대해 자세하게 적은 글이다. 다른건 다 필요없고 b^(x-2) ≡ b^-1 (mod X) 이 수식에서 b^(x-2) 이것을 구하는 것이 핵심이다. #풀이 #include #include using namespace std; using ll = l..
#문제 12865번: 평범한 배낭 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 #접근방법 모든 경우의 수를 따져야 하는 문제이다. 하지만 단순하게 백트래킹으로 접근하면 시간초과가 걸린다. 준서가 버틸 수 있는 무게가 100,000으로 제한이 되어있는 것에 초점을 두고 동적계획법으로 접근하면 된다. #풀이 #include #include using namespace std; i..
#문제 12851번: 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #접근방법 너비 우선 탐색(bfs) 알고리즘을 사용하면 풀 수 있다. #풀이 #include #include using namespace std; int visit[100005]; int main(){ int n,k; int ans1 = 987654321; intans2 = 0; queue q; scanf("%d %d",&n,..
#문제 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 모든 경우의 수를 구하는 백트래킹 기법으로 접근하면 된다. #풀이 #include int n,ans; intcol[15],updia[29],downdia[29]; void NQueen(int x){ for(int i=0;i
#문제 9251번: LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #접근방법 이전 배열의 값을 이용하는 동적계획법으로 접근하면 된다. #풀이 #include #include #include #include using namespace std; int arr[1005][1005]; int main(){ string a,b; int ans = 0; cin >> a >> b; for(int i=1;i
#문제 1916번: 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net #접근방법 이 문제는 어제 푼 문제랑 똑같은 문제이다. 다익스트라 알고리즘으로 최단비용을 구하면 된다. https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-CC [백준] 1753번 : 최단경로 [C..
#문제1753번: 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net #접근방법최단경로 알고리즘은 여러가지가 있다.다익스트라벨만 포드플로이드 워셜이 문제는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이므로 다익스트라 알고리즘을 사용하는 것이 적절하다. 다익스트라 알고리즘은 배열을 사용하는 방법과 우선순위 큐(힙 구조)를 사용하는 방법이 있다. 배열을 사용하는 ..
