728x90 누적합4 [python] 백준 2283 구간 자르기 https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 해결 리스트 인덱스를 x좌표로 하여 막대의 좌표 ( ex: (3,7)이면 vertical[3:7]에 +1씩 더해서 길이를 측정할 수 있도록 한다.)로 나타낸다. 원하는 만큼의 길이(k)가 안나오면 끝점(r)를 1씩 높여서 해당되는 길이만큼 증가시키고 그보다 크게 나오면 시작점(l)를 1씩 높여서 해당되는 길이만큼 줄이면서 원하는 값이 나오는.. 2023. 6. 26. [python] 백준 10800 컬러볼 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 문제 해결 우선 기준크기보다 크면 계산할 필요가 없으므로 sort()를 이용하여 공에 대한 정보를 공의 크기 오름차순으로 나타낸다. 크기가 기준크기보다 작아도 색이 같으면 계산에서 제외되므로 색깔별로 크기합에 대한 고려를 해야한다. 위의 생각을 통해 sort()를 한 후 for문으로 하나씩 기준을 잡는다. 이때 공의 크기가 작은 것부터 기준을 잡기 때문에 인덱스i 보다.. 2023. 5. 4. [python] 백준 9526 1의 개수 세기 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 문제해결 비트마스크 문제라는 것을 바로 알 수 있었다. (이진법을 이용한 1과 0을 이용해서 1의 개수를 세는 것이므로) 이진법에는 패턴이 있다. 0000-> 0001 ->0010->0011 ... (1의 자리수 01010101/ 2의 자리수 00110011 ....) 그 패턴을 써보고 풀어보면 바로 풀 수 있는 문제 CODE import math a, b = map(in.. 2023. 4. 13. [Python] 백준 25682 체스판 다시 칠하기 2 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 해결 1018번과 같은 유형이지만 시간초과 압박이 있다. https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 하지만 별 생각이 안나서 비슷하게 풀어 봤다. CODE i.. 2022. 12. 22. 이전 1 다음 728x90
