넘치게 채우기

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

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