기맹기 개발 블로그

BOJ 11066 파일 합치기 난이도 : 골드 3 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 전략 행렬 곱셈 순서 문제와 비슷한 유형이다. i ~ j까지의 파일을 합치는 최소 비용을 dp[i][j]로 하여 갱신시켜야 한다. 구하고자 하는 목표는 dp[1][K] 이므로 작은 문제부터 차근차근 올라오면 풀 수 있다. a ~ b 파일의 크기 합이 sum(a, b)라면 dp[i][j]는 다음과 같이 유도할 수 있다. dp[i][i] = ..

BOJ 9527 1의 개수 난이도 : 골드 2 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 전략 A, B 두 수의 최대 범위가 매우 크므로 무조건 패턴을 찾아서 공식을 만들어야 한다고 접근했다. 1자리 : 0 1 => 1 2자리 : 00 01 10 11 => 4 3자리 : 000 001 010 011 100 101 110 111 => 12 4자리 : 0000 0001 0010 0011 0100 0101 0110 01..

BOJ 10986 나머지 합 난이도 : 골드 3 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 전략 수열의 길이 N은 최대 10^6이므로 모든 부분 구간을 탐색하는 O(N^2)으로는 풀 수 없다. 누적 합을 이용하면 두 지점 사이의 부분 배열의 합을 구할 수 있다. 나는 누적합 % M이 반복되었을 때 해당 구간의 합 % M은 0이 되는 것을 주목했다. 문제의 예제를 예로 들어보자. N = 5, ..

BOJ 2143 두 배열의 합 난이도 : 골드 3 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 전략 처음에는 prefix sum을 구해놓고 포인터를 움직여가는 방식은 어떨까 생각해봤는데 배열이 두개라서 상당히 복잡할 것 같았다. 따라서 부배열 합들을 모두 저장해놓고 탐색하는 것이 좋겠다고 생각했다. 길이가 N인 배열에서 모든 부배열의 합을 구하는 것은 O(N^2..

BOJ 1806 부분합 난이도 : 골드 4 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 전략 수열의 길이 N이 최대 100,000이므로 당연히 O(N^2)으로 모두 탐색하는 것은 불가능하다. 투 포인터를 이용하여 O(N)에 배열의 연속된 부분합을 탐색할 수 있다. 시행착오 처음에는 하나의 loop 안에서 start와 end를 함께 옮기려고 했는데 조건문이 좀 복잡해진다. 따라서 둘 중 하나(코드에서는 start)를 루프의 기준..