https://jungol.co.kr/problem/8944시간 제한메모리 제한1초1024MB문제개의 물건 종류가 있으며, 각 물건은 다음 정보를 가진다.$W$: 무게$C$: 가치$K$: 최대 사용 가능 개수각 물건은 $0$개 이상 $K$개 이하로 선택할 수 있다.선택한 물건들의 총 무게는 $M$을 초과할 수 없다.총 무게가 $M$을 넘지 않도록 물건을 선택했을 때, 얻을 수 있는 가치의 최댓값을 구하라. 입력첫 줄에 정수 $N$, $M$이 주어진다.다음 $N$개의 줄에 정수 $W$, $C$, $K$가 주어진다.[제약 조건]$1 \le N \le 100$$1 \le M \le 10\,000$$1 \le W \le M$$1 \le C \le 10\,000$$1 \le K \le 10\,000$$W \tim..

https://jungol.co.kr/problem/2790시간 제한메모리 제한1초64MB문제병호가 ‘L’백화점에서 ‘N’타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다.병호가 ‘L’백화점에서 ‘N’타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다. 입력첫 번째 줄에는 출고한 타이어의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 각 타이어의 안지름 I, 바깥지름 O, 가격 P가 주어진다.1 ≤ I 출력병호가 팔 ..

https://jungol.co.kr/problem/2584시간 제한메모리 제한1초64MB문제전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다. 전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수 있지만 폭은 모두 동일하다고 가정한다. 각 그림에는 가격이 매겨져 있다.업체는 그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 전시대의 폭이 그림의 폭과 동일하여 겹쳐서 배치해야만 한다. 예를 들어, 위의 그림은 전시대에 네 개의 그림 A, B, C, D를 C, B, A, D의 순서로 겹쳐서 배치한 상황을 보여준다.위 그림의 오른쪽 부분은 전시된 그림들의 배치를 옆에서 본 모양을 나타내고, 왼쪽 부분은 배치한 그림들을 앞에서 보아서 관람객들이 보게 될 모양을 나타낸다. 그림 A는..

https://jungol.co.kr/problem/2264 시간 제한메모리 제한1초64MB문제색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다.미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다. 색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다.위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다.시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다. 주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보..

https://jungol.co.kr/problem/8356시간 제한메모리 제한2초512MB문제위 그림처럼 N 잔의 콜라들과 N 개의 피자 조각들이 일렬로 나열되어 있다.각 콜라들과 피자 조각들은 맛의 정도가 다 다른데, 이는 정수로 주어진다. 정올이는 이 중 1 잔의 콜라와, 1 개의 피자 조각을 선택하여 먹는다.항상 콜라는 왼손으로, 피자는 오른손으로 먹기에,선택된 피자 조각의 위치는 선택된 콜라의 위치보다 오른쪽에 있어야 한다. ( 인덱스가 더 커야 한다. )이 조건을 만족하면서 콜라와 피자 조각을 골랐을 때, 둘의 맛의 합이 최대가 되도록 하고 싶다. Q 개의 명령이 들어오는데, 세 가지 형태 중 하나로 들어온다.i 번째 콜라의 맛을 x 로 바꾼다.i 번째 피자 조각의 맛을 x 로 바꾼다.두 수 ..

https://jungol.co.kr/problem/4973?cursor=MTIsMSw0시간 제한메모리 제한6초 (ㅖ?)2048MB문제도시에 $N$명의 사람들이 살고 있다. 이 중 일부는 참말쟁이이고, 나머지는 거짓말쟁이이다.더욱 구체적으로, 참말쟁이들은 항상 옳은 말만을 하지만, 거짓말쟁이들은 옳은 말이든 거짓말이든 아무 말이나 한다.모든 사람들에게, 참말쟁이들이 이 도시에 몇 명이 존재하는지 물었다.그 결과, $i$번째 사람은 참말쟁이가 $A_i$명 이상 $B_i$명 이하라고 대답하였다.당신이 할 일은 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하는 것이다.그런데, 문제가 발생했다. 사람들의 기억력이 그리 좋지는 못하다는 것이다.$Q$번 증언이 바뀌며, $i$번째 증언 바뀜에서는 $P_i$..

class LazySegTree: def __init__(self, arr): self.n = len(arr) self.size = 1 while self.size >= 1 while node: stack.append(node) node >>= 1 for x in reversed(stack): self.push(x) def rebuild_path(self, node): """ node에서 루트까지 올라가며 값을 다시 계산한다. 업데이트 후 사용한다. """ node >>= 1 while node: ..

https://jungol.co.kr/problem/2387시간 제한메모리 제한초MB문제당신은 숲속에서 당신의 간식을 빼앗아간 원숭이 로봇을 쫓고 있다. 원숭이 로봇은 워낙 기민하게 움직이지만, 당신은 세계에서 가장 좋은 머신건을 이용하여 원숭이 로봇을 잡을 수 있다. 원숭이 로봇은 잡히지 않기 위해 어떤 나무 뒤에 숨는다.당신은 이러한 사실을 알고 있고 따라서 특정 나무를 골라서 그곳에 사격을 한다.당연히 세계에서 가장 좋은 총이기 때문에 나무는 쉽사리 뚫리게 되며, 만약 원숭이 로봇이 그 나무 뒤에 숨어 있을 경우 원숭이 로봇은 총을 맞아 작동이 멈추게 된다.만약 원숭이 로봇이 사격한 나무에 없을 경우 원숭이 로봇은 사격 소리를 듣고 조용히 이웃의 나무(한 번에 바로 이동할 수 있는 나무)로 이동하게..