보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.
한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.
상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.
상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 10^9, 1 ≤ M ≤ 300,000, M ≤ N)
다음 M개 줄에는 구간 [1, 10^9]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.
출력
첫째 줄에 질투심의 최솟값을 출력한다.
예제 입력
5 2
7
4
7 5
7
1
7
4
4
예제 출력
3
4
접근방식
질투심이 x일 때, 충족이 되는지만 구하면 된다. 즉, 이분 탐색으로 풀 수 있다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
long long a[300004], low = 1, high = 0, mid, result = 99999999;
bool check(long long mid)
{
long long num = 0;
for (int i = 0; i < m; i++)
{
num += a[i] / mid;
if (a[i] % mid)
{
num++;
}
}
return n >= num;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> a[i];
high = max(high, a[i]);
}
while (low <= high)
{
mid = (low + high) / 2;
if (check(mid))
{
result = min(result, mid);
high = mid - 1;
}
else
{
low = mid + 1;
}
}
cout << result;
return 0;
}
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.
(i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
아래 그림은 N = 3, M = 4인 경우이다.
원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.
다음 그림은 원판을 회전시킨 예시이다.
원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.
번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.
입력
첫째 줄에 N, M, T이 주어진다.
둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.
원판을 x배수 만큼 돌리고 인접한 수는 0으로 만들고 나머지 숫자들만 더하고 평균을 냈다.
원판을 돌릴때는 rotate함수를 사용하였다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };
int n, m, t, x, d, k, circle[54][54], visited[54][54], result;
bool flag = 1;
void _rotate(int y, int direction, int k)
{
vector<int> v;
for (int i = 0; i < m; i++)
{
v.push_back(circle[y][i]);
}
if (direction == 1)
{
rotate(v.begin(), v.begin() + k, v.end());
}
else
{
rotate(v.begin(), v.begin() + m - k, v.end());
}
for (int i = 0; i < m; i++)
{
circle[y][i] = v[i];
}
return;
}
void dfs(int y, int x)
{
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = (x + dx[i] + m) % m;
if (ny < 0 || ny >= n || visited[ny][nx]) continue;
if (circle[y][x] == circle[ny][nx])
{
visited[y][x] = visited[ny][nx] = 1;
flag = 0;
dfs(ny, nx);
}
}
}
bool findAdj()
{
flag = 1;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (circle[i][j] == 0 || visited[i][j]) continue;
dfs(i, j);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j])
{
circle[i][j] = 0;
}
}
}
return flag;
}
void setAverage()
{
int sum = 0;
int cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (circle[i][j] == 0) continue;
sum += circle[i][j];
cnt++;
}
}
double average = (double)sum / (double)cnt;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (circle[i][j] == 0) continue;
if ((double)circle[i][j] > average)
{
circle[i][j]--;
}
else if ((double)circle[i][j] < average)
{
circle[i][j]++;
}
}
}
return;
}
int main()
{
cin >> n >> m >> t;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> circle[i][j];
}
}
for (int i = 0; i < t; i++)
{
cin >> x >> d >> k;
for (int j = x - 1; j < n; j += x)
{
_rotate(j, d, k);
}
if (findAdj())
{
setAverage();
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
result += circle[i][j];
}
}
cout << result;
return 0;
}
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력
10
10 -4 3 1 5 6 -35 12 21 -1
10
2 1 -4 3 4 -4 6 5 -5 1
5
-1 -2 -3 -4 -5
예제 출력
33
14
-1
접근방식
구간을 더하면서 더한 수(sum)가 음수면은 더한 수(sum)을 버리고 계속 이어 나간다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int n, sum, a, result = -1001;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a;
sum += a;
result = max(result, sum);
if (sum < 0)
{
sum = 0;
}
}
cout << result;
return 0;
}
고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.
고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.
피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오
입력
첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.
출력
첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.
예제 입력
7
5 3
2
2
1
7
2
6
8
3
예제 출력
5
접근방식
누적합을 이용해서 푸는데 a에서 만들수 있는 경우의 수, b에서 만들수 있는 경우의 수, a와 b에서 꺼내서 만들수 있는 경우의 수를 더하면 된다.
코드
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int wantSize, n, m, a[1004], b[1004], psum_a[2008], psum_b[2008], result;
map<int, int> cnt_a, cnt_b;
void make(int n, int psum[], map<int, int>& cnt)
{
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n + i - 1; j++)
{
int sum = psum[j] - psum[j - i];
cnt[sum]++;
if (i == n) break;
}
}
return;
}
int main()
{
cin >> wantSize >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
psum_a[i] = psum_a[i - 1] + a[i];
}
for (int i = n + 1; i <= 2 * n; i++)
{
psum_a[i] = psum_a[i - 1] + a[i - n];
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
psum_b[i] = psum_b[i - 1] + b[i];
}
for (int i = m + 1; i <= 2 * m; i++)
{
psum_b[i] = psum_b[i - 1] + b[i - m];
}
make(n, psum_a, cnt_a);
make(m, psum_b, cnt_b);
for (int i = 1; i < wantSize; i++)
{
result += cnt_a[wantSize - i] * cnt_b[i];
}
result += cnt_a[wantSize];
result += cnt_b[wantSize];
cout << result;
return 0;
}
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.
낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
낚시왕이 오른쪽으로 한 칸 이동한다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
상어가 이동한다.
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.
상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.
입력
첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.
1. 사람이 움직이면서 상어를 잡는 처리 2. 상어가 움직이면서 상어를 먹는 처리 3. 벽에 부딪히면 방향 전환
방향이 1부터 시작하므로 {0,0,0,1,-1} 같이 크기가 5인 dx dy 필요 좌표도 1부터 시작하므로 1부터 시작하거나 -1을 하여 0으로 맞춰줘야함 temp를 통해서 상어가 계속 이동하는 것을 구현해서 현재 맵에 다시 덮어주기
코드
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct Shark
{
int x, y, s, z, dir, death;
}a[104 * 104];
const int dx[] = { 0, 0, 0, 1, -1 };
const int dy[] = { 0, -1, 1, 0, 0 };
int R, C, M, result, _map[104][104], temp[104][104];
int main()
{
cin >> R >> C >> M;
for (int i = 1; i <= M; i++)
{
cin >> a[i].y >> a[i].x >> a[i].s >> a[i].dir >> a[i].z;
a[i].y -= 1;
a[i].x -= 1;
_map[a[i].y][a[i].x] = i;
}
for (int t = 0; t < C; t++)
{
for (int y = 0; y < R; y++) // 이동하면서 상어 잡는 처리
{
if (_map[y][t])
{
a[_map[y][t]].death = 1;
result += a[_map[y][t]].z;
_map[y][t] = 0;
break;
}
}
memset(temp, 0, sizeof(temp));
for (int i = 1; i <= M; i++) // 상어가 움직이는 처리
{
if (a[i].death) continue;
int _y = a[i].y;
int _x = a[i].x;
int s = a[i].s;
int d = a[i].dir;
int ny, nx;
while (1) // 벽에 부딪히면 방향 전환
{
ny = _y + s * dy[d];
nx = _x + s * dx[d];
if (nx < C && ny < R && ny >= 0 && nx >= 0) break;
if (d == 1 && ny < 0)
{
s -= _y;
_y = 0;
d = 2;
}
else if (d == 2 && ny >= R)
{
s -= R - 1 - _y;
_y = R - 1;
d = 1;
}
else if (d == 3 && nx >= C)
{
s -= C - 1 - _x;
_x = C - 1;
d = 4;
}
else if (d == 4 && nx < 0)
{
s -= _x;
_x = 0;
d = 3;
}
}
if (temp[ny][nx])
{
if (a[temp[ny][nx]].z < a[i].z)
{
a[temp[ny][nx]].death = 1;
temp[ny][nx] = i;
}
else
{
a[i].death = 1;
}
}
else
{
temp[ny][nx] = i;
}
a[i].x = nx;
a[i].y = ny;
a[i].dir = d;
}
memcpy(_map, temp, sizeof(temp));
}
cout << result;
return 0;
}
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
출력
첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
예제 입력
2
5 6
0 0 1 0
3
3 4 5
1 0 1 0
6
1 2 3 4 5 6
2 1 1 1
예제 출력
30
30
35
17
54
-24
접근방식
연산자의 갯수를 하나씩 줄여가면서 연산자의 수가 모두 떨어질 때 까지 계산하면 된다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[12], b[4], p, minu, mult, divi, max_result = -1000000001, min_result = 1000000001;
void calculate(int idx, int cur, int plus, int minus, int mul, int div)
{
if (idx == n - 1)
{
max_result = max(cur, max_result);
min_result = min(min_result, cur);
return;
}
if (plus) calculate(idx + 1, cur + a[idx + 1], plus - 1, minus, mul, div);
if (minus) calculate(idx + 1, cur - a[idx + 1], plus, minus - 1, mul, div);
if (mul) calculate(idx + 1, cur * a[idx + 1], plus, minus, mul - 1, div);
if (div) calculate(idx + 1, cur / a[idx + 1], plus, minus, mul, div - 1);
return;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cin >> p >> minu >> mult >> divi;
calculate(0, a[0], p, minu, mult, divi);
cout << max_result << endl << min_result;
return 0;
}
