PS87 백준 11670 / C++ https://www.acmicpc.net/problem/11670 11670번: 초등 수학 입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다. a와 3개의 연산자(+ 혹은 - 혹은 *)중 하나, b 그리고 = 와 연산결과이다. 모든 연 www.acmicpc.net [ 풀이 ] 연산결과가 모두 다르게 짝지어야 한다. 이분매칭으로 해결해주면 된다. 이분그래프를 모델링할때 인덱스와 3가지 값을 연결시키면 될 것 같다. 근데 문제는 값이 음수도 나오고 큰 값이 나온다. 어차피 값의 개수는 7500개이하이므로 좌표압축으로 값의 인덱스를 연결시켜주면 된다. 이후 과정은 쉽다. [ Code ] #include using namespace std; usin.. 2022. 8. 17. 백준 1028 / C++ https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net [ 풀이 ] 한 점 (i,j)에서 왼쪽아래, 오른쪽 아래 대각선으로 최대로 긴 연속된 1의 개수를 저장해놓자. 다이아몬드의 비교는 한 점을 기준으로 min(왼쪽, 오른쪽)을 찾고 그 사이의 길이에 대해 탐색해주면 된다. 시간복잡도는 O(N^3/2)정도 된다. [ Code ] #include using namespace std; int n, m, a[777][777], dp[2][777][777]; int solve(int i, int j) { .. 2022. 8. 12. 백준 1493 / C++ https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net [ 풀이 ] 큐브들은 모두 작은걸로 큰걸 채울 수 있다. 따라서 그리디하게 길이에 맞는 가장 큰 큐브부터 사용하면 된다. (각 큐브가 작은것으로 큰걸 채우지 못하면 그리디를 사용할 수 없다.) 큐브를 사용했다면 박스는 세 부분으로 나뉜다. 이제 이 세부분으로 divide&conquer 해주면 된다. [ Code ] #include using namespace st.. 2022. 8. 12. 백준 11616 / C++ https://www.acmicpc.net/problem/11616 11616번: Digit Division We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m. Find the number of different suc www.acmicpc.net [ 풀이 ] 우선 짚고갈 것은 전체수가 m의 배수가 아니라면 m의 배수인 여러부분으로 분할할 수 없다. 이제 전체수.. 2022. 8. 12. 이전 1 ··· 8 9 10 11 12 13 14 ··· 22 다음