목록백준 (142)
mojo's Blog
[백준 1915] 가장 큰 정사각형
문제 링크 => 1915번: 가장 큰 정사각형 (acmicpc.net) 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 위와 같이 (i - 1, j - 1) 일때의 최대 넓이와 현재 (i, j) 로부터 왼쪽으로의 1의 최대 갯수와 윗쪽으로의 1의 최대 갯수를 활용하여 현재 (i, j) 의 원소가 0, 1인지를 구분하여서 접근하면 된다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define INF 100000000 using namespace s..
문제 링크 => 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 최대 전깃줄이 되도록 하려면 B전봇대로 연결된 전깃줄 중에 오름차순으로 연결될 수 있는 경우 중에 최댓값을 구해줘야 한다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int dp[501]; bool compare(pair x, pair y) { return..
문제 링크 => 11051번: 이항 계수 2 (acmicpc.net) 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 다이나믹 프로그래밍 문제이다. C(N, K) 를 이항계수 N(N-1)...(N-K+1) / 1*2*...*K 라고 할 때 Optimal substructure는 다음과 같다. K = 0 => C(N, K) = 1 K != 0 => C(N, K) = C(N, K-1) * (N - K + 1) / K % 10007 이 때 나누기 연산이 좀 거슬려 보인다. 여기서 10007은 prime 임을 이용하여 fermat's theorem 을 이용해 보도록 하자. x^(m-1) ..
문제 링크 => 1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 연습 문제이다. 전부 c로 구현하면 좋겠지만 priority_queue는 귀찮아서 stl로 가져와서 써먹었다. 만약에 priority_queue를 구현한다면 알고리즘 시간에 배웠던 heap을 이용하여 조건을 더 추가하여 만들면 된다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #..
[백준 10986] 나머지 합
문제 링크 => 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합을 이용한 문제이다. i 번째에서 j 번째까지 원소들의 합이 M으로 나누어 떨어지는 모든 경우를 구해야 한다. 이해하기 쉽도록 예시를 들어보도록 하자. ex ) 원소 5개 [1, 2, 3, 4, 5] 이 있고 3 으로 나누어 떨어지는 모든 경우의 수를 구하시오. 1. 배열 A에 대한 정보는 다음과 같다. 1 2 3 4 5 2. sum[i] = (..
[백준 2829] 아름다운 행렬
문제 링크 => 2829번: 아름다운 행렬 (acmicpc.net) 2829번: 아름다운 행렬 첫째 줄에 행렬의 크기 N이 주어진다. (2 ≤ N ≤ 400) 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다. www.acmicpc.net Brute Force 문제이다. 부 대각선에 대한 합들을 미리 구하여 모든 주 대각선을 탐색하면서 미리 구한 값들을 빼는 방식으로 접근했다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #define endl..