https://jungol.co.kr/problem/1479 시간 제한메모리 제한1초64MB문제최고 속력 600 km/h로 운행하는 것을 목표로 하는 ‘한국형 초고속철도 사업’이 순조롭게 진행되고 있다.이미 초고속철도의 시험선로를 구축하였고 열차를 시험운행하고 있다.그리고 선로의 상태를 검사하기 위하여, 선로의 지정된 검사구간을 담당하는 로봇을 설치하였다.그런데 검사구간이 서로 겹치는 로봇 사이에는 빈번한 데이터 교환이 필요하다.따라서 이를 지원할 데이터 송수신 장치를 모든 로봇에 설치할 뿐만 아니라, 특별한 데이터 처리장치를 로봇에 부착하기로 하였다.그러나 이 처리장치는 모든 로봇에 부착하지 않아도 되지만,두 로봇이 담당하고 있는 검사구간이 서로 겹치면 이 두 로봇 중에서 적어도 하나에는 반드시 부착되..

https://jungol.co.kr/problem/1858시간 제한메모리 제한1초256MB문제모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로 표현된다. 두 DNA 서열이 얼마나 비슷한가를 알아내기 위하여 유사도를 측정한다.두 DNA 서열의 유사도를 측정하기 위해서 먼저 각 서열의 임의의 위치에 공백을 넣어 길이를 같게 만든다. 이렇게 길이가 같아진 두 서열 간의 점수는 다음과 같이 계산된다. 같은 위치에 공백이 아닌 같은 문자가 있으면 3을 더한다.같은 위치에 서로 다른 문자가 있거나 둘 중 하나의 위치에 공백이 있으면 2를 뺀다.두 DNA 서열의 유사도는 각 DNA 서열의 임의의 위치에 공백을 넣어 위의 방법대로 얻을 수 있는 최대 점수이다.예를 들어 AGTCAG와 ATGTG라는 두 D..

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$..