넘치게 채우기

https://www.acmicpc.net/problem/1520BOJ - 내리막 길문제 유형: 다이나믹 프로그래밍, dfs문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 ..

BOJ - 케빈 베이컨의 6단계 법칙문제 유형: 플로이드-워셜문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교..

https://www.acmicpc.net/problem/28703BOJ - 28703 - Double It문제 유형: 정렬, 우선순위 큐, 슬라이딩 윈도우, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제양의 정수로 이루어진 길이가 N$N$인 배열 A1,⋯,AN이 주어집니다. 당신은 원하는 만큼 다음 조작을 할 수 있습니다.배열에서 원하는 수 하나를 골라서 2를 곱합니다.조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요. 입력첫 줄에 배열의 길이 N이 주어집니다. (1≤N≤200000)둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤10^9) 출력조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하..