algorithm14 백준 2407 조합 1. 문제 링크 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 2. 풀이 파스칼의 삼각형에서 제시하는 점화식을 활용해 DP방식으로 풀 수 있다. 문제는 long long 타입조차 감당 안될 정도로 숫자가 커진다는 것. 따라서 숫자 표현을 string으로 해야 한다. #include #include #include using namespace std; int n, m; string arr[101][101]; string StringPlus(const string& s1, const string& s2) { string result = ""; int tmp; a.. 2021. 10. 3. 백준 11779 최소비용 구하기 2 1. 문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이 전형적인 최단거리 문제이다. 다만 최소비용을 갖는 경로를 출력하는 부분이 추가되었다. 이 부분은 각 정점마다 최소 비용이 결정되는 시점에, 해당 정점으로 오기 바로 직전 정점을 별도의 배열에 표시해 둠으로 서 해결했다. //n(1≤n≤1,000)개의 도시 => 정점 //m(1≤m≤100,000)개의 버스 => 간선 #include #inc.. 2021. 10. 3. 백준 13549 숨바꼭질 3 1. 문제 링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 지금 위치에서 갈 수 있는 경우의 수와 비용은 아래와 같다. 이동: (지금 위치) * 2 비용: 0 이동: (지금 위치) - 1 비용: 1 이동: (지금 위치) +1 비용: 1 위 조건에서, N -> K로 이동하는 최단거리를 구하면 되는 문제이다. #include #include using namespace std; class Eleme.. 2021. 10. 3. 백준 2638 치즈 1. 문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 풀이 비어있는 곳을 탐색하도록 BFS를 수행하면서 치즈를 만날 때마다 그 위치에 카운트를 1 증가시킨다. 카운트를 증가시킬 때 마다 해당 위치의 누적 카운트를 측정해 2 이상이면 그 위치는 다음 턴에 제거될 위치로 선정한다. 제거될 위치에 있는 치즈를 제거 후 그 위치부터 다시 1번 과정을 반복한다. #include #include using namespace s.. 2021. 10. 2. 이전 1 2 3 4 다음