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를 어떤 자료 구조로 관리..

A 가지 한 두름 주세요 간단한 배열 탐색 문제. 10*10 크기의 작은 배열이기 때문에 그냥 브루트포스 돌려서 모든 행과 열을 탐색해 똑같은 문자로만 이루어진 행, 열이 존재하면 1, 아니면 0을 출력한다. D :rightplant: 정말 심각하게 시간 오래 끌어서 패널티 폭탄 맞은 문제. 양쪽으로 배열 관리를 하며 다음 수를 왼쪽에 넘겨줄지, 오른쪽에 넘겨줄지 결정한다. 결정 기준은 새로 추가될 숫자를 포함 왼쪽과 오른쪽의 차이가 가장 적게 나는 쪽으로 넘겨주면 된다. [left - 1 - right]와 같은 식으로 배열을 관리하면 되는데, 만약 left 총합 + 1보다 right 총합이 크거나 같다면 left의 모든 숫자들을 1씩 증가시키고 1을 left에 append. 아닌 경우는 반대로 righ..

시간 제한메모리 제한1초1024MB문제「Move or Block!」 게임은 N칸의 일자형 게임보드에서 할 수 있는 2인용 보드게임이다. 게임보드의 각 칸은 비어 있거나 벽이 세워져 있으며, 비어 있는 칸 중 하나에 두 플레이어가 움직일 수 있는 하나의 말을 올려두고 게임을 시작한다. 게임은 두 명의 플레이어가 턴을 번갈아 가면서 진행한다. 각 플레이어는 자신의 턴이 되었을 때 말의 인접한 칸에 모두 벽이 세워져 있으면 패배한다. 아니라면 아래 두 가지 행동 중 하나를 선택하여 한 번 플레이하고 턴을 넘긴다.말을 비어 있는 인접한 칸 중 하나로 움직인다.비어 있는 칸을 하나 골라 벽을 세운다.민규와 윤수가 「Move or Block!」 게임을 하려 한다. 주어진 게임보드에서 두 플레이어 모두 최적의 방법으..

시간 제한메모리 제한2초512MB문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다. 배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이성관이가 좋아하는 배열의 세 번째 조건을 그대로 사용하지 않고 부정을 취하는 것이..