넘치게 채우기

https://www.acmicpc.net/problem/1119BOJ - 그래프문제 유형: 그래프, MST(최소 신장 트리), dfs/bfs문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제N개의 도시가 있고, 몇몇 도시들이 양방향 도로로 연결되어 있는 나라가 있다. 은진이는 이나라의 도로 몇 개를 수정해서 모든 도시가 서로 연결되어 있게 하려고 한다. 이때, 도로를 수정하는 회수를 최소로 하려고 한다. 도로를 수정하는 방법은 다음과 같다.A와 B가 연결되어 있고, C와 D가 연결되어 있으면서, A와 C, A와 D, B와 C, B와 D가 연결되어 있지 않은 4개의 도시 A, B, C, D를 선택한다.A와 B를 연결하는 도로와 C와 D를 연결하는 도로를 없앤다.A와 C, B와 D를 연..

https://www.acmicpc.net/problem/2608BOJ - 로마 숫자문제 유형: 구현, 수학, 문자열문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제로마 시대 때는 현재 사용하는 아라비아 숫자가 아닌 다른 방법으로 수를 표현하였다.로마 숫자는 다음과 같은 7개의 기호로 이루어진다.기호IVXLCDM값1510501005001000수를 만드는 규칙은 다음과 같다.보통 큰 숫자를 왼쪽에 작은 숫자를 오른쪽에 쓴다. 그리고 그 값은 모든 숫자의 값을 더한 값이 된다. 예를 들어 LX = 50 + 10 = 60 이 되고, MLI = 1000 + 50 + 1 = 1051 이 된다.V, L, D는 한 번만 사용할 수 있고 I, X, C, M은 연속해서 세 번까지만 사용할 수 있다...

BOJ - 톱니바퀴(2)문제 유형: 구현, 시뮬레이션문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다.이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있..

https://www.acmicpc.net/problem/2812BOJ - 크게 만들기문제 유형: 모노토닉 스택, 스택, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ K 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 풀이두 가지 방법으로 풀었다:1. 우선순위 큐를 이용한 풀이N - K길이의 가장 큰 subsequence를 구하는 문제라고 볼 수도 있다.우선순위 큐의 요소로는 로 하고, 정렬 기준은 숫자에 대..

https://www.acmicpc.net/problem/9326BOJ - MI6문제 유형: 수학, 정수론, 소수판정문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제MI6는 스파이의 신원을 확인하기 위해서 스파이 식별 코드(Spy Identification Code, SIC)를 사용한다. 예를 들어, 제임스 본드의 SIC는 7이다.MI6는 스파이의 그룹과 그룹에 속하는 스파이를 쉽게 알아볼 수 있게 하기 위해 SIC를 할당한다. 그룹은 상태 코드로 나타낼 수 있는데, 상태 코드는 그룹에 속하는 모든 스파이의 SIC를 곱한 값이다.상태코드의 효율성을 위해, 2보다 크거나 같은 모든 상태코드에 대해서, 각 상태코드를 가지는 스파이 그룹이 유일하게 존재하고, 각 스파이 그룹사이의 상태코..

https://www.acmicpc.net/problem/14616BOJ - Explore Space문제 유형: 기하학, 수학, 정렬, 스위핑문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제지금으로부터 멀지 않은 미래 항성 간 이동이 가능해진 인류는 새로운 보금자리를 찾기 위한 여정을 떠난다. 긴 시간 끝에 마지막 웜홀을 눈앞에 두고 있지만 웜홀 안에는 방사능 층이 가득해 그냥 이용할 경우 수많은 사람들이 피폭당할 수 있다.다행히 인류에게는 방사능 층을 파괴할 수 있는 레이저를 가지고 있다. 레이저는 발사 위치로부터 반직선 형태로 발사되며 충돌하는 모든 방사능 층을 파괴할 수 있는 능력을 가지고 있다. 웜홀 안에 존재하는 방사능 층의 상태와 레이저의 발사 위치들이 주어졌을 때 레이저..

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가 서로 다르도록) 중위값과 평균..