시간 제한메모리 제한1초512MB문제https://www.acmicpc.net/problem/14750풀이다양한 알고리즘이 혼합된 문제다. 하지만 기본 개념 적용만 잘하면 까다로운 부분은 없어서 어렵지 않게 해결 할 수 있는 문제!..(맞나?) 문제에서 요구하는 것은 쥐구멍에 들어갈 수 있는 최대 쥐의 마릿 수다. 쥐는 쥐구멍까지 이어지는 일직선 상에 다른 벽과의 어떤 접점도 없어야만 해당 쥐구멍에 들어갈 수 있고, 각 쥐구멍에는 도망갈 수 있는 쥐의 수 제한이 있다. 우선은 쥐가 어떤 쥐구멍으로 도망갈 수 있는지 확인해야 한다.  1. 선분 교차 판정으로 쥐와 쥐구멍의 연결 여부 확인쥐의 위치를 m, 쥐구멍의 위치를 h, 벽의 양 끝 점을 a, b라고 하면 아래 그림과 같은 상황에서 ccw 값을 얻을 ..

시간 제한메모리 제한1초512MB문제UCPC에는 N명의 사람이 있다. 먼 옛날 쇼킹핫치킨에 대한 논쟁에서 시작된 이념의 대립으로 UCPC에는 kriii를 따르는 쇼킹핫진보 진영 A와, august14를 따르는 쇼킹핫보수 진영 B의 두 진영이 존재한다. 모든 사람은 둘 중 한 진영에 소속되어 있으며, 두 진영에 동시에 들어가는 것은 불가능하다. i번 사람과 j번 사람에 대해 서로 다른 진영에 들어가게 될 경우 슬픈 정도 w[i, j]가 주어진다. 일부 사람들은 쇼킹핫에 관한 자신의 철학이 강해 무조건 A진영에 들어가는 사람도 있고, 무조건 B진영에 들어가는 사람도 있다. 물론 치킨은 무엇이든 옳으므로 두 진영 어디에 가든 상관없는 사람도 있다. N명의 사람들이 적절히 두 진영에 나누어 들어갈 때, 슬픔 정..

시간 제한메모리 제한2초1024MB문제사람들이 N행 M열의 직사각형 모양으로 모여 있다. 초기에 각각의 사람의 상태는 정상 체온이거나 저체온증이고, 낮과 밤을 지나면서 사람들의 상태가 변화한다.낮은 따뜻하기 때문에 저체온증인 사람이 정상 체온으로 회복할 수 있는 기회이다. 어떤 사람과 사방으로 인접한 두 명 이상의 사람이 정상 체온이라면 따뜻한 체온을 나눠 받아 저체온증에서 정상 체온으로 회복된다. 어떤 사람이 정상 체온으로 회복된 후에는 같은 방법으로 인접한 다른 사람들이 정상 체온으로 회복할 수 있으며, 이러한 체온 회복 과정은 낮 사이에 충분히 많이 반복될 수 있다.밤은 춥기 때문에 정상 체온인 사람들이 저체온증에 걸릴 수 있다. 단, 밤 사이에 새롭게 저체온증에 걸리는 사람은 K명 이하이다.낮과 ..

23829번: 인문예술탐사주간태영이는 SASA의 축제라고 불리는 "인문예술탐사주간"을 보내게 되었다. "인문예술탐사주간"을 맞이하여 세종호수공원에 가게 된 태영이는 아름다운 경치에 놀라움을 금치 못했다. 세종호수공원www.acmicpc.net 만약 태영이의 위치가 0이라면 사진의 점수는 모든 나무의 위치 총합이 된다.태영이의 위치가 X일 때, X 오른쪽 나무들로 얻는 점수는 각 나무의 위치에서 X를 뺀 값의 총 합이 된다. X 왼쪽 나무들의 점수는 X에서 나무의 위치를 뺀 값의 총합이 된다. 결국 점수는 특정 위치로부터의 누적합이 되는 셈이다. i번째 나무까지의 누적합을 prepix[i]에 저장한다. 그림으로 보면 아래와 같다. 태영이가 13에 있다면 a와 b는 이렇게 그려볼 수 있다. 파란색이 빼야 하..

시간 제한메모리 제한1초128MB문제학생회장을 하고 있는 상근이는 이번 학교 축제 행사로 학우들간의 친밀감을 돈독히 하고자 줄다리기를 하려 한다. 하지만 이 줄다리기에 형평성을 최대한 고려하기위해 두 팀간의 사람 수 차이를 1 이하로 하려하며, 두 팀간의 몸무게의 차이가 최소화되도록 하고자 한다. 이때 상근이가 나누려 하는 두 팀의 몸무게를 각각 출력 하시오. 입력가장 첫 번째 줄에 줄다리기를 하기 원하는 총 인원의 수(1 ≤ N ≤ 100)가 주어진다. 이후 N개의 줄에 줄다라기에 참여하기 원하는 사람의 몸무게(1 ≤ K ≤ 450)가 주어진다. 출력두팀의 몸무게를 작은 순서대로 순차적으로 출력한다. 풀이N명이 주어졌을 때, 한 팀에 있을 수 있는 최대 인원은 N//2명 또는 N//2+1명이다. 여기서..

시간 제한메모리 제한1초128MB문제대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다. 대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다) 고속도로가 서로 교차하..

시간 제한메모리 제한2초512MB문제(그림생략)사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다. 사다리..

시간 제한메모리 제한2초512MB문제자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다. 유형 1 : S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 입력첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니다. (1 ≤ X ≤ 2,000,000) T가 2라면 X는 S에서 삭제해야 할 몇 번째로 작은 수인지를 나타냅니다. S에 최소 X개의 원소가 있음이 보장됩니다. 출력유형 2의 쿼리 개수만큼의 줄에 각 쿼리에 대한 답을 출력합니다. 풀이S를 어떤 자료 구조로 관리..