Dev_Diary

https://www.acmicpc.net/problem/1797 1797번: 균형잡힌 줄서기 첫째 줄에는 한 줄로 선 팬들의 수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 그 다음 N개의 줄에는 남녀의 성별을 나타내는 수(남자는 0, 여자는 1)와 이들이 서있는 x좌표가 공백으로 구분되어 주어진다. x www.acmicpc.net 누적합과 해시맵을 함께 써서 풀 수 있는 문제입니다. 남여의 성별 코드가 ( 0 ,1 ) 로 존재하는데 이를 ( -1, 1 ) 로 치환하면, 즉 남자의 성별코드를 -1 로 치환하면 누적합을 통해 남여의 수가 같은 구간을 쉽게 구할 수 있습니다. 당연히 한 줄로 서있기 때문에 x 값을 기준으로 정렬해주어야 합니다. 인덱스 1 2 3 4 5 6 7 8 9 성별 남(-1) ..

https://www.acmicpc.net/problem/15554 15554번: 전시회 승원이는 미술품 N개를 가지고 있다. 각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. i번 미술품의 크기는 Ai, 가치는 Bi로 나타낸다. 오늘은 승원이의 저택 1층에서 미술품을 전시하려고 www.acmicpc.net 우선 최대 무게와 최소 무게를 지정했다고 가정하겠습니다. 그렇다면 두 미술품 사이에 정렬되어 있는 미술품은 모두 전시하는 것이 S - (A_max - A_min) 의 값을 크게 만듭니다. A_max 와 A_min 은 고정되어 있는 반면 S 는 값이 커지기 때문입니다. 그렇다면 어느 미술품을 고를 때, 크기별로 정렬되어 있다면 연속된 구간을 모두 선택하는 것이 최적의 해를 구하는 방법이라고 할 수..

https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이 www.acmicpc.net 직사각형을 작은 세 개의 직사각형으로 자르는 문제입니다. 네 개의 꼭짓점을 세 개의 직사각형이 나누어 차지하는 문제로 생각해보면 두 개의 꼭짓점을 가지는 직사각형 + 한 개의 꼭짓점을 가지는 직사각형 두 개 로 나눌 수 밖에 없다는 것을 알 수 있습니다. 그렇기 때문에 한 변을 포함하는 직사각형을 미리 지정하고 나머지 덩어리를 세로 혹은 가로로 잘라보는 과정을 방향별로 네 번 반복해주..