아롱이의 PS하는 블로그

[Python] 백준 9527 - 1의 개수 세기

문제두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. $$\sum_{x=A}^{B}{f(x)}$$ 입력첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ $10^{16}$)출력1의 개수를 세어 출력한다. 풀이사실 누적합, dp 그런거 다 필요없다.약간의 관찰을 하면 자리수별로 1의 개수를 직접 계산할 수 있다! 일단 A, B를 받는다.그리고, 0부터 N까지 1의 개수를 카운팅하는 함수 sol()를 만들고, 최종적인 결과로 sol(B) - sol(A-1)을 출력하도록 하자. 좋다. 이제 어떤 수..

[파이썬으로 구현하는] 세그먼트 트리(Segment Tree) - Top-Down

"파이썬으로 구현하는"시리즈 2세그먼트 트리(Segment Tree)Top-Down오늘은 파이썬으로 구현하는 세그먼트 트리에 대해서 알아볼 것이다. 먼저 세그먼트 트리가 무엇인지 알아보자. 가끔씩 우리는 어떤 수열에서 연속한 부분에 대한 쿼리를 처리해주어야 할 때가 있다.예를 들어, [3, 1, 4, 1, 5, 9, 2] 라는 수열이 있다고 하자. 인덱스는 0부터 시작한다.그리고, 인덱스 a부터 b까지 구간합을 구하는 쿼리가 주어진다.여기까지는 딱히 새로운 자료구조 없이 누적합을 이용하면 쿼리가 아무리 많아도 쉽게 구할 수 있을 것이다. 그런데, 이번에는 저 리스트의 특정 인덱스의 값을 다른 값으로 변화시키는 쿼리가 들어왔다.이런 경우에는 일일이 누적 합 배열을 다시 구하고 있어야 한다! 이런 경우(구간..

"파이썬으로 구현하는"시리즈 1분리 집합(Disjoint Set)오늘은 파이썬으로 구현하는 분리 집합의 표현 방법에 대해서 알아볼 것이다. 다른 말로 유니온-파인드 자료 구조(Union-Find Structure)라고도 하는 이 자료구조는, 집합의 묶음을 관리하는 구조이다. 여기에서 집합은 서로소 집합으로, 한 원소가 둘 이상의 집합에 속하는 경우가 없다. 아이디어는 다음과 같다. 집합 하나당 원소 하나가 대표값이 된다.그래서, 같은 집합에 속해있으면 같은 대표값을 가지게 되는 것이다! 예를 들어, 집합이 {3, 1, 4}, {5} {6, 7, 8, 9}인 경우 다음과 같이 나타낼 수 있을 것이다.  예를 들어서 나는 이 상태에서 {3, 1, 4}와 {6, 7, 8, 9} 집합을 합하고 싶다. 그러면 어..

https://www.acmicpc.net/problem/1419문제첫 항이 x이고 공차가 d인 등차수열의 첫 k개의 항은 x, x+d, x+2d, ..., x+(k-1)d이다. x와 d가 자연수인 등차수열의 첫 k개의 항의 합으로 나타낼 수 있는 수 중에서, l 이상이고 r 이하인 수가 몇 개인지 구하는 프로그램을 작성하시오.입력자연수 l, r, k가 순서대로 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ 1,000,000,000, 2 ≤ k ≤ 5)출력첫째 줄에 조건을 만족하는 수의 개수를 출력한다.  풀이등차수열의 합 공식은 무엇인가?첫 항이 x이고 공차가 d라면, 등차수열의 k개의 합은  $$\frac{k(2x+(k-1)d)}{2}$$  로 나타낼 수 있다.여기서 $l$ 이상이고 $r$..

https://www.acmicpc.net/problem/3679 문제평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.입력첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트..

https://www.acmicpc.net/problem/30645문제탁자 위에 인형을 전시하려고 한다. 탁자는 위에서 보았을 때 R개의 행과 C개의 열을 가진 R × C개의 칸을 가진 2차원 배열이며, 각 칸에 하나의 인형을 전시할 수 있다. 현재 전시할 수 있는 인형은 N개이며, 탁자 위에 N개의 인형을 모두 전시할 필요는 없다.탁자를 정면으로 보면 1행에 놓은 인형들이 맨 앞쪽에 있는 방향으로 보게 되는데, 같은 열에 있는 인형들에 대해 앞쪽 행에 인형을 놓은 경우 앞쪽 인형보다 뒤쪽 행에 있고 높이가 앞쪽 인형의 높이 이하인 인형은 앞쪽 인형에 가려져 보이지 않게 된다.이때, 탁자에 인형들을 적당히 배치했을 때 탁자의 정면 방향에서 보이는 인형의 개수의 최댓값을 구하는 프로그램을 작성하시오.입력첫..

https://www.acmicpc.net/problem/14247문제영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n$n$일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.입력첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.다음 줄에는 ..

https://www.acmicpc.net/problem/4008문제1부터 n까지 번호가 붙여진 n명의 병사들로 이루어진 군대의 지휘관이 있다. 이 지휘관은 앞으로의 전투를 위하여 n명의 병사들을 여러 개의 특공대로 나누고자 한다. 결속력과 사기를 높이기 위하여 각 특공대는 {i, i+1, ..., i+k}형태의 번호가 연속하는 병사들로 구성된다.각 병사 i의 전투력은 xi이다. 병사들 {i, i+1, ..., i+k}로 구성된 특공대의 전투력 x는 원래는 각 병사의 전투력의 합으로 계산되었다. 달리 말하면 x = xi + xi+1 + ... + xk이었다.그러나 여러 해의 영광스러운 승리를 통하여 특공대의 전투력을 다음과 같이 조정해야 하는 것으로 결론을 내렸다: 특공대의 조정된 전투력 x′는 등식 x..

https://www.acmicpc.net/problem/14751문제There are two distinct horizontal lines hupper and hlower in the xy-coordinate plane and n line segments connecting them. One endpoint of each segment lies on hupper and the other on hlower. All endpoints of the segments are distinct. All segments are numbered from 1 to n. Consider a horizontal line hi located between hupper and hlower, which will be given ..

https://www.acmicpc.net/problem/13263문제높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다.i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비..