https://www.acmicpc.net/problem/25589시간 제한메모리 제한1초1024MB문제N*N 크기의 격자 위에 칸마다 코인이 놓여있다.푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오. 입력첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^..

시간 제한메모리 제한2초1024MB문제정점이 N개가 있는 트리가 있고 각 정점들은 1부터 N까지 번호가 매겨있다. 해당 트리로부터 (N-2)개의 양의 정수로 이루어진 수열 하나를 다음과 같은 과정을 통해서 만들 것이다.차수가 1인 정점들 중에서 번호가 가장 큰 정점을 하나 고른다. 해당 정점을 x라고 부르자.정점 x와 인접한 정점의 번호를 수열에 넣는다.정점 x와 인접한 간선들을 해당 트리에서 지운다.1번부터 3번까지의 과정을 총 (N - 2)번 진행한다.수열 {a1, ... , aN-2}가 주어졌을 때, 위의 과정을 통해서 이 수열을 만들 수 있는 트리를 구하여라.입력다음과 같이 입력이 주어진다.Na1 ··· aN-2 출력해당 트리가 존재한다면 간선 (N-1) 개를 다음 규칙에 만족하게 출력한다.각 간..

https://www.acmicpc.net/problem/8895시간 제한메모리 제한1초256MB문제높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자.위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만드는 배치의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, l, r이..

시간 제한메모리 제한1초512MB문제농부 존의 N마리의 소들은 각각 2차원 농장의 서로 다른 위치 (x1, y1)...(xN, yN)에 서 있습니다(1 ≤ N ≤ 1,000), 그리고 xi와 yi는 1,000,000 이하의 양의 홀수입니다). 농부 존은 x=a 방정식을 가진 남북 방향의 긴(사실상 무한한 길이의) 울타리를 지어 그의 농장을 분할하고 싶어합니다. (a는 짝수여야 하며, 이는 어떤 소의 위치에도 울타리가 지어지지 않도록 보장합니다). 또한 그는 y=b 방정식을 가진 동서 방향의 긴(사실상 무한한 길이의) 울타리를 짓고 싶어합니다. 여기서 b도 짝수입니다. 이 두 울타리는 점 (a,b)에서 교차하며, 함께 그의 농장을 네 개의 영역으로 나눕니다. 농부 존은 네 개의 영역에 있는 소들이 적절하게..

시간 제한메모리 제한2초128MB문제https://www.acmicpc.net/problem/1827윤화의 직장은 여행을 온 사람들을 버스에서 안내하는 여행 가이드이다. 윤화는 어느 날 다른 날과 다름없이 N명의 사람을 버스 안에서 인솔을 하게 되었다. 그러던 도중 점심시간을 갖게 되었다. 점심시간은 한 시간인데 그 시간동안에는 N명의 사람들은 각자 자기가 가고 싶은 곳으로 갈 수 있다. 한 시간 뒤에 사람들을 버스에서 모이기로 약속을 하고 모두 흩어졌다. 그런데 일이 발생하고 말았다. 한 시간이 흘렀는데 사람들이 아무도 버스에 돌아오지 않은 것이다. 윤화는 흩어진 사람들을 모두 만나서 빨리 버스로 돌아가라고 말을 해 주고 버스로 돌아가야 한다. (단, 그 말을 들은 사람은 그 즉시 자신의 이동 방향을 ..

시간 제한메모리 제한1초128MB문제*이 문제는 실제 인물과는 관련이 없습니다.* 옛날 먼 옛날, 사냐라는 사람이 살았습니다. 사냐라는 사람은 뢰벗이라는 친구가 있었는데, 둘은 매우 닮았지만, 뢰벗이 좀 더 똑똑하고, 사냐가 좀 더 잘생겼다고 합니다. 뢰벗은 오보워치(Ovorwatch) 라는 게임에서 500점으로 상위 100.00%였습니다. 사냐는 이러한 뢰벗을 놀리기를 좋아했습니다. 이에 열을 받은 뢰벗은, 사냐에게 자신이 오보워치 500점을 탈출한다면, 자신이 내는 문제를 평생 풀도록 하겠다는 내기를 했고, 사냐는 뢰벗이 설마 탈출하겠냐는 생각으로 수락했습니다. 그런데 그 일이 벌어졌습니다. 뢰벗은 오보워치 점수를 무려 600점대 까지 올렸고, 사냐는 내기 때문에 뢰벗이 내는 문제를 평생 풀어야 하게..

시간 제한메모리 제한1.2초1024MB문제(요약함)0번 항이 1, 1번항이 1로 시작되는 피보나치 수열을 두고 길이 N의 수열A에 대한 쿼리가 주어진다. 수열 A는 초기에 모든 값이 0으로 되어있으며 첫 번째 항을 1번 항, 마지막 항을 N번 항으로 한다. 쿼리는 l, r로 N이하인 두 개의 자연수로 주어진다. l은 항상 r이하임이 보장된다. 쿼리는 수열 A의 l번 항부터 r번 항을 피보나치 수열의 1번 항부터 r-l+1번 항까지로 바꾸는 작업이다. 입력첫째 줄에는 수열의 크기 N이 주어진다. N은 100만 이하의 자연수이다.둘째 줄에는 쿼리의 수 Q가 주어진다. Q는 100만 이하의 자연수이다.셋째 줄 부터 Q줄에 걸친 쿼리가 주어진다. 출력모든 쿼리를 순서대로 적용한 후 수열 A의 모든 항을 공백으로..

시간 제한메모리 제한1초1024MB문제종민이는 CTP 초등학교 5학년 3반 담임 교사로 일하고 있다. 최근 들어 CTP 초등학교에 전학을 오는 5학년 학생들이 많아져서, 대책으로 종민이가 담당하는 3반을 2개 분반으로 나누기로 했다. 종민이는 이전부터 자신이 담당하는 반의 학생들로부터 고통을 받고 있었다. 5학년 3반 친구들은 수업 시간임에도 불구하고 친구들끼리 놀면서 수업을 듣기를 거부하는 일이 많기 때문에, 5학년 3반의 분반은 종민이에게 매우 희소식이었다. 종민이는 5학년 3반의 모든 친한 친구인 두 학생을 서로 다른 분반에 배치하여 고통을 줄이려고 한다. 하지만 그런 배치가 불가능한 경우도 있기 때문에, 이를 위해 한가지 묘책을 생각해 냈다. 그것은 바로 친한 친구 관계인 두 학생이 서로 험담을 ..