넘치게 채우기

https://www.acmicpc.net/problem/10881BOJ - 프로도의 선물 포장문제 유형: 브루트 포스문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제프로도는 네오에게 줄 생일 선물을 세 개 샀다. 이 세 개의 선물은 직사각형 모양의 선물 상자에 각각 하나씩 담겨 있다. 프로도는 이 선물들을 적당한 크기의 직사각형 포장 상자에 넣어 포장하려 한다. 큰 포장 상자를 주문할수록 돈을 더 많이 써야 하기 때문에, 프로도는 최대한 작은 상자에 세 개의 선물을 모두 담으려고 한다.사용하게 될 포장 상자의 크기는 선물 상자의 배치 방법에 따라 달라질 수 있다. 이때, 선물들이 안전하게 포장되기 위해서는 각 변이 상자의 가로와 세로에 평행하게 해야 하고, 선물 상자 전체가 포장..

https://www.acmicpc.net/problem/1823BOJ - 수확문제 유형: 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제1 × N 크기의 긴 밭에 벼가 심어져 있다. 준희는 이 벼를 수확 하려고 한다. 그런데 가운데 있는 벼를 수확을 하려면 끝에서 가운데까지 헤집고 들어가야 하므로 양 끝에 있는 벼만 수확을 할 수 있다. 처음에는 첫 번째와 N번째 벼를 수확을 할 수 있을 것이며 만약에 첫 번째 벼를 수확을 하였다면 두 번째 벼와 N번째 벼를 수확을 할 수 있다.수확을 하였을 때 얻을 수 있는 이익은 다음과 같다. 만약에 그 벼의 가치가 v(i)라고 하고 그 벼를 k번째로 수확을 한다고 하면 v(i) × k 만큼의 이익을 얻게 된다.만약에 벼..

https://www.acmicpc.net/problem/22868BOJ - 산책(small)문제 유형: bfs, 그래프, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다.현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 가장 짧은 거리와 E에서 S로 가는 가장 짧은 거리를 원한다.정점 S에서 정점 E로 이동할 때, 가장 짧은 ..

https://www.acmicpc.net/problem/2405BOJ - 세 수, 두 M문제 유형: 그리디, 정렬, 수학문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제n개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c)÷3이 된다.만약 세 수가 5, 2, 5라면 중위값은 5, 평균값은 4가 된다. 세 수가 2, 3, 1이라면 중위값은 2, 평균값도 2가 된다.n개의 수들이 주어졌을 때, 위와 같이 세 수를 선택하여(i, j, k가 서로 다르도록) 중위값과 평균..

https://www.acmicpc.net/problem/2285BOJ - 우체국문제 유형: 그리디, 정렬문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다. 입력첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X..

https://www.acmicpc.net/problem/5829BOJ - Luxury River Cruise문제 유형: dfs/bfs, 그래프, 희소 배열문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 At each port, the tour guides choose either the "left" river or the "right" river to sail down next, but they keep repeating the same choices over and over. Mo..

https://www.acmicpc.net/problem/14925BOJ - 목장 건설하기문제 유형: 구간합, 다이나믹 프로그래밍, 히스토그램, 모노토닉 스택문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다.그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다. 랜드씨의 땅에서 지을 ..

https://www.acmicpc.net/problem/1898BOJ - 이전 수열은 어떤 수열일까문제 유형: 그리디문제 난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제길이 n의 수열 S가 주어진다. S는 1부터 n까지의 n개 정수를 임의 순서로 늘어놓은 것이다. 다음 조건을 만족하는 수열들 중 오름차순으로 가장 앞에 오는 수열이 무엇인지 궁금하다. 이를 알아내는 프로그램을 작성하라.1부터 n까지의 정수를 임의 순서로 늘어놓은 수열이다.이 수열의 i번째 수 와 원래 수열 S의 i번째 수 의 차는 1을 넘을 수 없다. 입력첫 줄에 수열의 길이 n이 주어진다. (3 ≤ n ≤ 50,000) 이후 n개의 줄에 수열을 이루는 수가 한 개씩 차례대로 주어진다. 출력n개의 줄에 걸쳐, 조건을 ..

https://www.acmicpc.net/problem/29726BOJ - 숏코딩의 왕 브실이문제 유형: 그리디, 애드 혹문제 난이도: Gold V시간 제한: 1초메모리 제한: 1024MB 문제숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 A1,A2,⋯,AN로 주어진다.브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열의 길이가 L일 때, 행복도를 계산하는 방법은 다음과 같다. 브실이는 행복도를 늘리고자 자신의 코드 길이 수열에서 최대 M개까지 제출 기록을 없앨 수 있다.최대 M개의 제출 기록을 없앴을 때 브실이가 얻을 수 있는 행복도의 최댓값을 구해보자. 단, 행복도는 음수가 될 수 있다. 입력첫 번째 줄에 정수 N, M이 공백으로 구분되어 ..

https://www.acmicpc.net/problem/1117BOJ - 색칠 1문제 유형: 수학, 구현문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제지민이는 종이에 색칠하기를 좋아한다. 지민이는 W×H 크기의 직사각형 종이를 가지고 있다. 지민이는 종이에 다음과 같이 색칠 하려고 한다.종이를 x = f에 맞춰서 접는다. 이때, 왼쪽 종이가 오른쪽 종이 위에 올라오게 접는다.종이를 가로로 c+1개의 크기가 동일 한 구간으로 나눈다. 그 다음에 c번 가장 위의 구간부터 차례대로 접는다.왼쪽 아래가 (x1, y1) 이고, 오른쪽 위가 (x2, y2)인 직사각형을 찾는다. 이때, (0, 0)은 현재 접힌 상태에서 가장 왼쪽 아래 점이다. 그 직사각형을 칠한다. 이때, 페인트는 겹쳐있는..