알고리즘225 BOJ 17037 - Painting the barn (발상, 누적합) https://www.acmicpc.net/problem/17037 1000이하의 자연수로 표현되는 좌표평면에 최대 1e5개의 직사각형모양 페인트를 칠할것. k와 좌하단(x1,y1), 우상단(x2,y2)꼭지점으로 표현되는 직사각형들이 주어질 때, 페인트가 정확히 k겹 칠해진 부분의 넓이를 구해라. int a[1001][1001] -> a[i][j]: 칸(i,j)에 페인트가 칠해진 횟수 직사각형이 최대 1e5개이므로, 직사각형 정보가 들어올 때마다 a[i][j]를 초기화하면 최악의 경우 1e5*1e3*1e3이므로 시간초과가 난다. 가로줄,세로줄을 따로 초기화한다는 아이디어가 필요하다. 처음엔 위쪽 경계선은 -1로, 아래쪽은 +1로 초기화 해둔다. 그 후 전체를 초기화한다. 말로하기가 어렵지만 코드를 눈으로.. 2020. 2. 22. BOJ 9359 - 서로소 (포함배제) https://www.acmicpc.net/problem/9359 포함배제에 대한 자세한 설명: https://zzonglove.tistory.com/35 a,b,n이 주어진다. a,b사이의 수 중 n과 서로소인 수의 개수를 구하여라. (n> tt; for (int tc = 1; tc > a >> b >> n; ll ans = b - a + 1; //n 2020. 2. 22. BOJ 15757 - Out of sorts (세그 트리) https://www.acmicpc.net/problem/15757 .. 일반적인 버블소트는 한 라운드당 한번씩 어떤 원소를 오른쪽으로 최대한 밀어준다. 문제에서의 소트는 추가로 어떤 원소를 최대한 왼쪽으로 밀어준다. 숫자배열이 주어질때, 배열이 정렬되려면 최소 몇번의 라운드가 필요한지 구하라 사이트 solution 풀이 Input array A: 1 8 5 | 3 2 Sorted version: 1 2 3 | 5 8 i i+1 위처럼 구간을 둘로 나누는 선을 생각해서, 선 왼쪽의 sorted에 포함되는 동시에 선 오른쪽의 원래 배열에 포함되는 최대 원소 수를 구해주면 된다. 숫자는 여러번 나올수있고 범위가 넓으므로 숫자의 index를 기준으로 파악해주면 된다. const int MAX = 1e5 + 4.. 2020. 2. 20. BOJ1517 - 버블소트 (inversion count) https://www.acmicpc.net/problem/1517 주어진 숫자배열을 버블소트할 때 swap연산의 회수를 nlogn시간에 구하라 https://justicehui.github.io/ps/2019/04/23/BOJ1517/ 이분 풀이 참고 ll n, a[MAX], b[MAX], ans; void msort(int st, int en) { if (st == en) return; int mid = (st + en) / 2; msort(st, mid); msort(mid + 1, en); ll i = st, j = mid+1, k = 0, cnt=0; while (i 2020. 2. 20. 이전 1 ··· 14 15 16 17 18 19 20 ··· 57 다음