[アルゴリズム]sds特別テーマ指導コード1
48038 ワード
1713 #include <cstdio>
int n; // 사진틀의 갯수
int pic_frame[20]; // 사진틀(자료구조) 0 ~ 19 index를 갖는다
int num_cc; // 추천갯수
int ord_cc[1000]; // 추천 순서
int cand_like[101]; //후보 추천 횟수
int cand_where[101]; // 후보가 어떤 사진틀에 걸려있는 지
int cand_when[101]; // 후보가 사진틀에 언제 올라갔는지
int get_pic_frame() {
// 잘 구현하는 것과
// 조건을 찾다보면 뭔가 하나 빠져있음 변수가...
for (int i = 0 ; i < n ; i++) {
if (pic_frame[i] == 0) return i;
}
// 올라가있는 후보중에서 좋아요가 가장 작은후보
// 같으면 오래전에 올라간후보
int res = 0; // 최종 반환할 사진틀의 위치
int min_like = 1000; // 올라간 후보중에서 좋아요가 가장 작은 값을 얻기 위한 값
int old_when = 1000; // 올라간 시간이 가장 오래된 값을 찾기 위한 값
for (int i = 0 ; i < n ; i++) {
int cur = pic_frame[i];
int tmp_like = cand_like[cur];
int tmp_when = cand_when[cur];
if (tmp_like < min_like) {
min_like = tmp_like;
old_when = tmp_when;
res = i;
}
else if (tmp_like == min_like && tmp_when < old_when) {
min_like = tmp_like;
old_when = tmp_when;
res = i;
}
}
return res;
}
int main() {
freopen("res/B1713.in", "r", stdin);
scanf("%d", &n);
scanf("%d", &num_cc);
for (int i = 0 ; i < num_cc ; i++) {
scanf("%d", &ord_cc[i]);
}
// 초기화
for (int i = 1 ; i <= 100 ; i++) {
cand_where[i] = -1;
cand_when[i] = -1;
}
// 추천을 수행한다 .... num_cc만큼
for (int i = 0 ; i < num_cc ; i++) {
// ord_cc[i]
int cur = ord_cc[i];
// 후보가 사진틀에 올라가 있을까?
if (cand_where[cur] != -1) {
// 좋아요만 올려줌
cand_like[cur]++;
}
else {
// 비어있는 또는 후보를 넣을 사진틀을 얻는다.
int pos = get_pic_frame();
int delete_cand = pic_frame[pos];
// delete_cand는 사진틀에서 내리면서, 좋아요도 초기화한다
if (delete_cand != 0) {
cand_where[delete_cand] = -1;
cand_like[delete_cand] = 0;
}
cand_where[cur] = pos;
cand_like[cur] = 1;
cand_when[cur] = i;
pic_frame[pos] = cur;
}
}
// 정답을 출력한다
// pic_frame을 조사해서, 누가 사진틀에 있는지확인하고,
// 후보들을 모아서 번호가 증가하는 순서대로 출력한다..
for (int i = 1 ; i <= 100 ; i++) {
if (cand_where[i] != -1) {
printf("%d ", i);
}
}
}
1920 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int M;
private static int[] A;
private static int[] Q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
Q = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < M ; i++) {
Q[i] = Integer.parseInt(st.nextToken());
}
// sorting
Arrays.sort(A);
// cpp
// #include <algorithm>
// sort(a, a + n);
// binary search
for (int i = 0 ; i < M ; i++) {
System.out.println(binary_search(Q[i]));
}
}
// 있으면 1
// 없으면 0
public static int binary_search(int key) {
int left, right, mid;
left = 0;
right = N - 1;
while (left <= right) {
mid = (left + right) / 2;
if (A[mid] == key) {
return 1;
}
else if (key < A[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return 0;
}
}
1039 #include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int tonum(char arr[]) {
int res = 0;
for (int i = 0 ; arr[i] ; i++) {
res *= 10;
res += arr[i] - '0';
}
return res;
}
int conv(int num, int l, int r) {
// l과 r의 체크가 안되어있음
// 처음에 num의 자리수는 정해져있기때문에 그걸 이용하면 됨
// arr
char buf[16];
sprintf(buf, "%d", num);
char tmp;
// swap
tmp = buf[l];
buf[l] = buf[r];
buf[r] = tmp;
// 앞자리가 0이 아닌지 체크도..
if (buf[0] == '0') return 0;
return tonum(buf);
}
int n, k;
bool isok(int num) {
// 예외가 되는 것들은 바로처리
// 1 ~ 9 ==> 교환이 안됨 ==> -1
if (num < 10) return false;
// 10, 20, .. .90 ==> 교환이 안됨 ==> -1
if (num < 100 && num % 10 == 0) return false;
return true;
}
int get_num_len(int num) {
int len = 0;
while (num > 0) {
len++;
num /= 10;
}
return len;
}
int main() {
// todo - 완전탐색
// 숫자를 직접 교환하는 로직
// 교환해서 단계별로 탐색해가는 로직
// 그리고 답 구하면 됨
scanf("%d%d", &n, &k);
if (n == 1000000) {
printf("%d", n);
return 0;
}
if (!isok(n)) {
printf("-1");
return 0;
}
queue<int> q;
q.push(n);
for (int i = 0 ; i < k ; i++) {
// q --> next_q --> q
// 단계별로 처리하기 위해서
// 다음번 작업을 하기전에 임시로 저장하는 곳이고
// q size를 이용해서 어찌어찌 처리를 하면 필요가 없어요 ==> 고민해보시면 됨
vector<int> next_q;
while (!q.empty()) {
int cur = q.front();
q.pop();
int len = get_num_len(cur);
for (int s = 0 ; s < len ; s++) {
for (int e = s + 1 ; e < len ; e++) {
int next_num = conv(cur, s, e);
if (next_num == 0) continue;
// 꼭 다 넣어야할까????
// 현재 다음번 처리는 "중복"이 발생하고 있습니다
// 적절하게 처리해 중복을 피해봅시다
next_q.push_back(next_num);
}
}
}
for (int i = 0 ; i < next_q.size() ; i++) {
q.push(next_q[i]);
}
}
// k번을 돌렸기 때문에 q에남아 있는 것들은 k번을 수행하고 남은 숫자들이고
// q에 남은것 중에 가장 큰것을 출력하면 됨
int ans = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (ans < cur) ans = cur;
}
printf("%d", ans);
}
1759 import java.io.*;
import java.util.*;
public class Main {
private static int L, C;
private static char[] arr;
private static char[] ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
ans = new char[L];
arr = new char[C];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < C ; i++) {
String str = st.nextToken();
arr[i] = str.charAt(0);
}
Arrays.sort(arr);
recur(0, 0);
}
public static void recur(int where, int from) {
// final condition
if (where == L) {
if (check()) {
System.out.println(new String(ans));
}
return;
}
for (int i = from ; i < C ; i++) {
ans[where] = arr[i];
// public static void recur(int where, int from)
// 이 점에 미리 자음이랑 모음 개수를 세어놓을 수 있다.
// 중간에 잘하면 가지치기도 가능
recur(where + 1, i + 1);
}
}
public static boolean check() {
int countMoeum = 0, countJaeum = 0;
boolean[] isMoeum = new boolean[128];
isMoeum['a'] = true;
isMoeum['e'] = true;
isMoeum['i'] = true;
isMoeum['o'] = true;
isMoeum['u'] = true;
for (int i = 0 ; i < L ; i++) {
if (isMoeum[ans[i]]) countMoeum++;
else countJaeum++;
}
return countMoeum >= 1 && countJaeum >= 2;
}
}
1103 #include <cstdio>
int n, m, ans, dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1}, limit;
int max_count[50][50]; // 시작부터 가장 많이 점프 한 횟수
char board[50][51];
void dfs(int y, int x, int cnt) {
if (ans < cnt) ans = cnt;
if (ans > limit) return;
// 예외 처리
if (y < 0 || n <= y || x < 0 || m <= x || board[y][x] == -1) return;
if (cnt <= max_count[y][x]) return;
max_count[y][x] = cnt;
int mul = board[y][x];
for (int i = 0 ; i < 4 ; i++) {
dfs(y + dy[i] * mul, x + dx[i] * mul, cnt + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
limit = n * m;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < m ; j++) {
// 처음 시작 점프 횟수가 0일 예정이라서 0보다 작은 -1로 초기화를 했는데,
// 다른 방식으로도 구현이 가능합니다.
max_count[i][j] = -1;
}
}
for (int i = 0 ; i < n ; i++) {
scanf("%s", board[i]);
for (int j = 0 ; j < m ; j++) {
if (board[i][j] == 'H') board[i][j] = -1;
else board[i][j] -= '0';
}
}
dfs(0, 0, 0);
if (ans > limit) ans = -1;
printf("%d", ans);
}
2580 #include <cstdio>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii> empty_space;
int sudoku[9][9];
// pos에 있는 empty_space를 어떤숫자로 채울지 판단
void recur(int pos) {
// final condition
if (pos == empty_space.size()) {
// 출력하고
// 끝냄
return;
}
for (int i = 0 ; i <= 9 ; i++) {
// 앞으로 할 일은 empty_space를 0 ~ 9 로 채워보는 건데
// 언제채울 수 있냐면
// 1. empty_space가 있는 작은 사각형에 숫자가 중복이 안될때! ==> 그 작은 사각형을 어떻게 판단할지
// 2. empty_space가 있는 세로줄에 숫자가 중복이 안될때 ==> 세로줄을 어떻게 판단할지??
// 3. empty_spcae가 있는 가로줄에 숫자가 중복이 안될때 ==> 가로줄을 어떻게 판단할지???
// 1, 2, 3이 만족이 되면 일단 "그 숫자"로 채워보고
recur(pos + 1);
// 만약에 정답을 찾았으면 끝내는 방향으로 가고
// 못찾았으면 다른 숫자로 채워보고...
}
}
int main() {
// 입력을 받은 다음에
// 빈 공간들("0")을 모은다 (y, x) --> empty_space
// 모든 empty_space를 어떤 값으로 다 채웠다고 판단하면 그 상태가 정답이므로 출력을 한다.
}
1339 #include <cstdio>
#include <vector>
using namespace std;
int n, alpha_cnt; // alpha_cnt : 서로다른 알파벳의 갯수
int ans;
char word[10][10];
bool check[128];
bool used[10];
int mapping[10];
vector<char> alpha;
// mapping 0 1 2 3 4 5 ==> 순열로 나열할 것임
// value 9 7 1 2 5 6
// alpha Z A X Y D E
// 알파벳에 매핑된 숫자를 반환
int toNum(char c) {
for (int i = 0 ; i < alpha_cnt ; i++) {
if (alpha[i] == c) {
return mapping[i];
}
}
return 0;
}
// k번째 문자열을 숫자로 반환
int getNum(int k) {
int res = 0;
//"ABCDE"
//"98765"
//9 98 987 9876 98765
for (int i = 0 ; word[k][i] !=0 ; i++) {
int num = toNum(word[k][i]);
res *= 10, res += num;
}
return res;
}
int calc() {
int sum = 0;
for (int i = 0 ; i < n ; i++) {
sum += getNum(i);
}
return sum;
}
// 매핑된 숫자로 뭔가 계산
// 알파벳에 매핑할 숫자들 경우를 일이 구해보는 것
void brute_force(int who) {
// final condition
if (who == alpha_cnt) {
int tmp = calc();
if (ans < tmp) {
ans = tmp;
}
// debug
/*
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%c ", alpha[i]);
}
printf("\n");
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%d ", mapping[i]);
}
printf("\n");
printf("\n");
*/
return;
}
for (int i = 0 ; i <= 9 ; i++) {
if (used[i]) continue;
used[i] = true;
mapping[who] = i;
brute_force(who + 1);
mapping[who] = 0; // 꼭 하지는 않아도 됨
used[i] = false;
}
}
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", word[i]);
// 문자열 끝까지 읽는 다는 뜻(마지막 값은 0임 C++에서)
for (int j = 0 ; word[i][j] != 0 ; j++) {
if (!check[word[i][j]]) {
alpha_cnt++;
check[word[i][j]] = true;
alpha.push_back(word[i][j]);
}
}
}
// 작업 - 숫자들을 하나씩 매핑 해보는 경우의 수
brute_force(0);
printf("%d", ans);
}
// 알파벳이 주어지면
// 알파벳별로 숫자를 하나씩 매핑해보는게 일입니다.
// 최대 10개가 주어지는데....경우의수?????
// 이렇게 만든 경우의수에 대해서
// 직접 숫자을 대입해서 합을구하고, 최대값을 찾는다....
// 두번째 ==> 숫자를 그대로이용하는 방법
// ABCD : 1000 * A + 100 * B + 10 * C + D
// GCD : 100 * G + 10 * C + D
// EFABC : 10000 * E + 1000 * F + 100 * A + 10 * B + C
// ----------------------------------------------------
// 1100 * A + 110 * B + 21 * C + 2 * D + 10000 * E + 1000 * F + 100 * G
2003 import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static int[] A;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
// 완전탐색 비슷하게
// 투포인터는??
int s = 0, e = 0, sum = 0;
for (s = 0 ; s < N ; s++) {
for ( ; e < N ; e++) {
sum += A[e];
System.out.printf("[s ~ e] %d %d : %d\n", s, e, sum);
if (sum == M) {
answer++;
break;
}
else if (sum > M) {
break;
}
}
sum -= A[s];
}
System.out.println(answer);
}
}
2805 #include <cstdio>
typedef long long LL;
int n, m;
LL tree[1000000];
LL answer;
bool cutok(LL h) {
LL sum = 0;
for (int i = 0 ; i < n ; i++) {
if (tree[i] > h) {
sum += tree[i] - h;
}
if (sum >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) {
scanf("%lld", &tree[i]);
}
// 높이를 변경해가면서 나무를 잘라보고
// 조건을 만족하는 가장 큰 높이를 찾아본다.....
// 시간 초과가 발생할 것 같음
/*
for (LL h = 0 ; h <= 1000000000 ; h++) {
if (cutok(h)) {
answer = h;
}
else {
break;
}
}
*/
LL bottom = 0, top = 1000000000, mid;
while (bottom <= top) {
mid = (bottom + top) / 2;
if (cutok(mid)) {
if (answer < mid) answer = mid;
bottom = mid + 1;
}
else {
top = mid - 1;
}
}
printf("%lld", answer);
}
1072 import java.io.*;
import java.util.*;
public class Main {
private static long X, Y, Z;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
Z = Y * 100 / X;
if (Z == 100 || Z == 99) {
System.out.println(-1);
return;
}
// 이분 탐색으로 진행
long bottom = 1, top = 1000000000, mid;
long answer = 1000000000;
while (bottom <= top) {
mid = (bottom + top) / 2;
long nextZ = (Y + mid) * 100 / (X + mid);
if (Z < nextZ) {
if (mid < answer) {
answer = mid;
}
top = mid - 1;
}
else {
bottom = mid + 1;
}
}
System.out.println(answer);
//System.out.println("Z : " + Z);
//System.out.println("NEXT Z : " + (Y + answer) * 100 / (X + answer));
/*
// 경기횟수가 정수 범위를 벗어 난다면??????
for (int i = 1 ; ; i++) {
long nextZ = (Y + i) * 100 / (X + i);
double tmp = (double)(Y + i) * 100 / (X + i);
System.out.println(tmp);
if (nextZ != Z) {
System.out.println(i);
break;
}
}
*/
}
}
7453 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}
2842 #include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}
11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
int n; // 사진틀의 갯수
int pic_frame[20]; // 사진틀(자료구조) 0 ~ 19 index를 갖는다
int num_cc; // 추천갯수
int ord_cc[1000]; // 추천 순서
int cand_like[101]; //후보 추천 횟수
int cand_where[101]; // 후보가 어떤 사진틀에 걸려있는 지
int cand_when[101]; // 후보가 사진틀에 언제 올라갔는지
int get_pic_frame() {
// 잘 구현하는 것과
// 조건을 찾다보면 뭔가 하나 빠져있음 변수가...
for (int i = 0 ; i < n ; i++) {
if (pic_frame[i] == 0) return i;
}
// 올라가있는 후보중에서 좋아요가 가장 작은후보
// 같으면 오래전에 올라간후보
int res = 0; // 최종 반환할 사진틀의 위치
int min_like = 1000; // 올라간 후보중에서 좋아요가 가장 작은 값을 얻기 위한 값
int old_when = 1000; // 올라간 시간이 가장 오래된 값을 찾기 위한 값
for (int i = 0 ; i < n ; i++) {
int cur = pic_frame[i];
int tmp_like = cand_like[cur];
int tmp_when = cand_when[cur];
if (tmp_like < min_like) {
min_like = tmp_like;
old_when = tmp_when;
res = i;
}
else if (tmp_like == min_like && tmp_when < old_when) {
min_like = tmp_like;
old_when = tmp_when;
res = i;
}
}
return res;
}
int main() {
freopen("res/B1713.in", "r", stdin);
scanf("%d", &n);
scanf("%d", &num_cc);
for (int i = 0 ; i < num_cc ; i++) {
scanf("%d", &ord_cc[i]);
}
// 초기화
for (int i = 1 ; i <= 100 ; i++) {
cand_where[i] = -1;
cand_when[i] = -1;
}
// 추천을 수행한다 .... num_cc만큼
for (int i = 0 ; i < num_cc ; i++) {
// ord_cc[i]
int cur = ord_cc[i];
// 후보가 사진틀에 올라가 있을까?
if (cand_where[cur] != -1) {
// 좋아요만 올려줌
cand_like[cur]++;
}
else {
// 비어있는 또는 후보를 넣을 사진틀을 얻는다.
int pos = get_pic_frame();
int delete_cand = pic_frame[pos];
// delete_cand는 사진틀에서 내리면서, 좋아요도 초기화한다
if (delete_cand != 0) {
cand_where[delete_cand] = -1;
cand_like[delete_cand] = 0;
}
cand_where[cur] = pos;
cand_like[cur] = 1;
cand_when[cur] = i;
pic_frame[pos] = cur;
}
}
// 정답을 출력한다
// pic_frame을 조사해서, 누가 사진틀에 있는지확인하고,
// 후보들을 모아서 번호가 증가하는 순서대로 출력한다..
for (int i = 1 ; i <= 100 ; i++) {
if (cand_where[i] != -1) {
printf("%d ", i);
}
}
}import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int M;
private static int[] A;
private static int[] Q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
Q = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < M ; i++) {
Q[i] = Integer.parseInt(st.nextToken());
}
// sorting
Arrays.sort(A);
// cpp
// #include <algorithm>
// sort(a, a + n);
// binary search
for (int i = 0 ; i < M ; i++) {
System.out.println(binary_search(Q[i]));
}
}
// 있으면 1
// 없으면 0
public static int binary_search(int key) {
int left, right, mid;
left = 0;
right = N - 1;
while (left <= right) {
mid = (left + right) / 2;
if (A[mid] == key) {
return 1;
}
else if (key < A[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return 0;
}
}1039 #include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int tonum(char arr[]) {
int res = 0;
for (int i = 0 ; arr[i] ; i++) {
res *= 10;
res += arr[i] - '0';
}
return res;
}
int conv(int num, int l, int r) {
// l과 r의 체크가 안되어있음
// 처음에 num의 자리수는 정해져있기때문에 그걸 이용하면 됨
// arr
char buf[16];
sprintf(buf, "%d", num);
char tmp;
// swap
tmp = buf[l];
buf[l] = buf[r];
buf[r] = tmp;
// 앞자리가 0이 아닌지 체크도..
if (buf[0] == '0') return 0;
return tonum(buf);
}
int n, k;
bool isok(int num) {
// 예외가 되는 것들은 바로처리
// 1 ~ 9 ==> 교환이 안됨 ==> -1
if (num < 10) return false;
// 10, 20, .. .90 ==> 교환이 안됨 ==> -1
if (num < 100 && num % 10 == 0) return false;
return true;
}
int get_num_len(int num) {
int len = 0;
while (num > 0) {
len++;
num /= 10;
}
return len;
}
int main() {
// todo - 완전탐색
// 숫자를 직접 교환하는 로직
// 교환해서 단계별로 탐색해가는 로직
// 그리고 답 구하면 됨
scanf("%d%d", &n, &k);
if (n == 1000000) {
printf("%d", n);
return 0;
}
if (!isok(n)) {
printf("-1");
return 0;
}
queue<int> q;
q.push(n);
for (int i = 0 ; i < k ; i++) {
// q --> next_q --> q
// 단계별로 처리하기 위해서
// 다음번 작업을 하기전에 임시로 저장하는 곳이고
// q size를 이용해서 어찌어찌 처리를 하면 필요가 없어요 ==> 고민해보시면 됨
vector<int> next_q;
while (!q.empty()) {
int cur = q.front();
q.pop();
int len = get_num_len(cur);
for (int s = 0 ; s < len ; s++) {
for (int e = s + 1 ; e < len ; e++) {
int next_num = conv(cur, s, e);
if (next_num == 0) continue;
// 꼭 다 넣어야할까????
// 현재 다음번 처리는 "중복"이 발생하고 있습니다
// 적절하게 처리해 중복을 피해봅시다
next_q.push_back(next_num);
}
}
}
for (int i = 0 ; i < next_q.size() ; i++) {
q.push(next_q[i]);
}
}
// k번을 돌렸기 때문에 q에남아 있는 것들은 k번을 수행하고 남은 숫자들이고
// q에 남은것 중에 가장 큰것을 출력하면 됨
int ans = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (ans < cur) ans = cur;
}
printf("%d", ans);
}
1759 import java.io.*;
import java.util.*;
public class Main {
private static int L, C;
private static char[] arr;
private static char[] ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
ans = new char[L];
arr = new char[C];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < C ; i++) {
String str = st.nextToken();
arr[i] = str.charAt(0);
}
Arrays.sort(arr);
recur(0, 0);
}
public static void recur(int where, int from) {
// final condition
if (where == L) {
if (check()) {
System.out.println(new String(ans));
}
return;
}
for (int i = from ; i < C ; i++) {
ans[where] = arr[i];
// public static void recur(int where, int from)
// 이 점에 미리 자음이랑 모음 개수를 세어놓을 수 있다.
// 중간에 잘하면 가지치기도 가능
recur(where + 1, i + 1);
}
}
public static boolean check() {
int countMoeum = 0, countJaeum = 0;
boolean[] isMoeum = new boolean[128];
isMoeum['a'] = true;
isMoeum['e'] = true;
isMoeum['i'] = true;
isMoeum['o'] = true;
isMoeum['u'] = true;
for (int i = 0 ; i < L ; i++) {
if (isMoeum[ans[i]]) countMoeum++;
else countJaeum++;
}
return countMoeum >= 1 && countJaeum >= 2;
}
}
1103 #include <cstdio>
int n, m, ans, dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1}, limit;
int max_count[50][50]; // 시작부터 가장 많이 점프 한 횟수
char board[50][51];
void dfs(int y, int x, int cnt) {
if (ans < cnt) ans = cnt;
if (ans > limit) return;
// 예외 처리
if (y < 0 || n <= y || x < 0 || m <= x || board[y][x] == -1) return;
if (cnt <= max_count[y][x]) return;
max_count[y][x] = cnt;
int mul = board[y][x];
for (int i = 0 ; i < 4 ; i++) {
dfs(y + dy[i] * mul, x + dx[i] * mul, cnt + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
limit = n * m;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < m ; j++) {
// 처음 시작 점프 횟수가 0일 예정이라서 0보다 작은 -1로 초기화를 했는데,
// 다른 방식으로도 구현이 가능합니다.
max_count[i][j] = -1;
}
}
for (int i = 0 ; i < n ; i++) {
scanf("%s", board[i]);
for (int j = 0 ; j < m ; j++) {
if (board[i][j] == 'H') board[i][j] = -1;
else board[i][j] -= '0';
}
}
dfs(0, 0, 0);
if (ans > limit) ans = -1;
printf("%d", ans);
}
2580 #include <cstdio>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii> empty_space;
int sudoku[9][9];
// pos에 있는 empty_space를 어떤숫자로 채울지 판단
void recur(int pos) {
// final condition
if (pos == empty_space.size()) {
// 출력하고
// 끝냄
return;
}
for (int i = 0 ; i <= 9 ; i++) {
// 앞으로 할 일은 empty_space를 0 ~ 9 로 채워보는 건데
// 언제채울 수 있냐면
// 1. empty_space가 있는 작은 사각형에 숫자가 중복이 안될때! ==> 그 작은 사각형을 어떻게 판단할지
// 2. empty_space가 있는 세로줄에 숫자가 중복이 안될때 ==> 세로줄을 어떻게 판단할지??
// 3. empty_spcae가 있는 가로줄에 숫자가 중복이 안될때 ==> 가로줄을 어떻게 판단할지???
// 1, 2, 3이 만족이 되면 일단 "그 숫자"로 채워보고
recur(pos + 1);
// 만약에 정답을 찾았으면 끝내는 방향으로 가고
// 못찾았으면 다른 숫자로 채워보고...
}
}
int main() {
// 입력을 받은 다음에
// 빈 공간들("0")을 모은다 (y, x) --> empty_space
// 모든 empty_space를 어떤 값으로 다 채웠다고 판단하면 그 상태가 정답이므로 출력을 한다.
}
1339 #include <cstdio>
#include <vector>
using namespace std;
int n, alpha_cnt; // alpha_cnt : 서로다른 알파벳의 갯수
int ans;
char word[10][10];
bool check[128];
bool used[10];
int mapping[10];
vector<char> alpha;
// mapping 0 1 2 3 4 5 ==> 순열로 나열할 것임
// value 9 7 1 2 5 6
// alpha Z A X Y D E
// 알파벳에 매핑된 숫자를 반환
int toNum(char c) {
for (int i = 0 ; i < alpha_cnt ; i++) {
if (alpha[i] == c) {
return mapping[i];
}
}
return 0;
}
// k번째 문자열을 숫자로 반환
int getNum(int k) {
int res = 0;
//"ABCDE"
//"98765"
//9 98 987 9876 98765
for (int i = 0 ; word[k][i] !=0 ; i++) {
int num = toNum(word[k][i]);
res *= 10, res += num;
}
return res;
}
int calc() {
int sum = 0;
for (int i = 0 ; i < n ; i++) {
sum += getNum(i);
}
return sum;
}
// 매핑된 숫자로 뭔가 계산
// 알파벳에 매핑할 숫자들 경우를 일이 구해보는 것
void brute_force(int who) {
// final condition
if (who == alpha_cnt) {
int tmp = calc();
if (ans < tmp) {
ans = tmp;
}
// debug
/*
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%c ", alpha[i]);
}
printf("\n");
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%d ", mapping[i]);
}
printf("\n");
printf("\n");
*/
return;
}
for (int i = 0 ; i <= 9 ; i++) {
if (used[i]) continue;
used[i] = true;
mapping[who] = i;
brute_force(who + 1);
mapping[who] = 0; // 꼭 하지는 않아도 됨
used[i] = false;
}
}
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", word[i]);
// 문자열 끝까지 읽는 다는 뜻(마지막 값은 0임 C++에서)
for (int j = 0 ; word[i][j] != 0 ; j++) {
if (!check[word[i][j]]) {
alpha_cnt++;
check[word[i][j]] = true;
alpha.push_back(word[i][j]);
}
}
}
// 작업 - 숫자들을 하나씩 매핑 해보는 경우의 수
brute_force(0);
printf("%d", ans);
}
// 알파벳이 주어지면
// 알파벳별로 숫자를 하나씩 매핑해보는게 일입니다.
// 최대 10개가 주어지는데....경우의수?????
// 이렇게 만든 경우의수에 대해서
// 직접 숫자을 대입해서 합을구하고, 최대값을 찾는다....
// 두번째 ==> 숫자를 그대로이용하는 방법
// ABCD : 1000 * A + 100 * B + 10 * C + D
// GCD : 100 * G + 10 * C + D
// EFABC : 10000 * E + 1000 * F + 100 * A + 10 * B + C
// ----------------------------------------------------
// 1100 * A + 110 * B + 21 * C + 2 * D + 10000 * E + 1000 * F + 100 * G
2003 import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static int[] A;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
// 완전탐색 비슷하게
// 투포인터는??
int s = 0, e = 0, sum = 0;
for (s = 0 ; s < N ; s++) {
for ( ; e < N ; e++) {
sum += A[e];
System.out.printf("[s ~ e] %d %d : %d\n", s, e, sum);
if (sum == M) {
answer++;
break;
}
else if (sum > M) {
break;
}
}
sum -= A[s];
}
System.out.println(answer);
}
}
2805 #include <cstdio>
typedef long long LL;
int n, m;
LL tree[1000000];
LL answer;
bool cutok(LL h) {
LL sum = 0;
for (int i = 0 ; i < n ; i++) {
if (tree[i] > h) {
sum += tree[i] - h;
}
if (sum >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) {
scanf("%lld", &tree[i]);
}
// 높이를 변경해가면서 나무를 잘라보고
// 조건을 만족하는 가장 큰 높이를 찾아본다.....
// 시간 초과가 발생할 것 같음
/*
for (LL h = 0 ; h <= 1000000000 ; h++) {
if (cutok(h)) {
answer = h;
}
else {
break;
}
}
*/
LL bottom = 0, top = 1000000000, mid;
while (bottom <= top) {
mid = (bottom + top) / 2;
if (cutok(mid)) {
if (answer < mid) answer = mid;
bottom = mid + 1;
}
else {
top = mid - 1;
}
}
printf("%lld", answer);
}
1072 import java.io.*;
import java.util.*;
public class Main {
private static long X, Y, Z;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
Z = Y * 100 / X;
if (Z == 100 || Z == 99) {
System.out.println(-1);
return;
}
// 이분 탐색으로 진행
long bottom = 1, top = 1000000000, mid;
long answer = 1000000000;
while (bottom <= top) {
mid = (bottom + top) / 2;
long nextZ = (Y + mid) * 100 / (X + mid);
if (Z < nextZ) {
if (mid < answer) {
answer = mid;
}
top = mid - 1;
}
else {
bottom = mid + 1;
}
}
System.out.println(answer);
//System.out.println("Z : " + Z);
//System.out.println("NEXT Z : " + (Y + answer) * 100 / (X + answer));
/*
// 경기횟수가 정수 범위를 벗어 난다면??????
for (int i = 1 ; ; i++) {
long nextZ = (Y + i) * 100 / (X + i);
double tmp = (double)(Y + i) * 100 / (X + i);
System.out.println(tmp);
if (nextZ != Z) {
System.out.println(i);
break;
}
}
*/
}
}
7453 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}
2842 #include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}
11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int tonum(char arr[]) {
int res = 0;
for (int i = 0 ; arr[i] ; i++) {
res *= 10;
res += arr[i] - '0';
}
return res;
}
int conv(int num, int l, int r) {
// l과 r의 체크가 안되어있음
// 처음에 num의 자리수는 정해져있기때문에 그걸 이용하면 됨
// arr
char buf[16];
sprintf(buf, "%d", num);
char tmp;
// swap
tmp = buf[l];
buf[l] = buf[r];
buf[r] = tmp;
// 앞자리가 0이 아닌지 체크도..
if (buf[0] == '0') return 0;
return tonum(buf);
}
int n, k;
bool isok(int num) {
// 예외가 되는 것들은 바로처리
// 1 ~ 9 ==> 교환이 안됨 ==> -1
if (num < 10) return false;
// 10, 20, .. .90 ==> 교환이 안됨 ==> -1
if (num < 100 && num % 10 == 0) return false;
return true;
}
int get_num_len(int num) {
int len = 0;
while (num > 0) {
len++;
num /= 10;
}
return len;
}
int main() {
// todo - 완전탐색
// 숫자를 직접 교환하는 로직
// 교환해서 단계별로 탐색해가는 로직
// 그리고 답 구하면 됨
scanf("%d%d", &n, &k);
if (n == 1000000) {
printf("%d", n);
return 0;
}
if (!isok(n)) {
printf("-1");
return 0;
}
queue<int> q;
q.push(n);
for (int i = 0 ; i < k ; i++) {
// q --> next_q --> q
// 단계별로 처리하기 위해서
// 다음번 작업을 하기전에 임시로 저장하는 곳이고
// q size를 이용해서 어찌어찌 처리를 하면 필요가 없어요 ==> 고민해보시면 됨
vector<int> next_q;
while (!q.empty()) {
int cur = q.front();
q.pop();
int len = get_num_len(cur);
for (int s = 0 ; s < len ; s++) {
for (int e = s + 1 ; e < len ; e++) {
int next_num = conv(cur, s, e);
if (next_num == 0) continue;
// 꼭 다 넣어야할까????
// 현재 다음번 처리는 "중복"이 발생하고 있습니다
// 적절하게 처리해 중복을 피해봅시다
next_q.push_back(next_num);
}
}
}
for (int i = 0 ; i < next_q.size() ; i++) {
q.push(next_q[i]);
}
}
// k번을 돌렸기 때문에 q에남아 있는 것들은 k번을 수행하고 남은 숫자들이고
// q에 남은것 중에 가장 큰것을 출력하면 됨
int ans = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (ans < cur) ans = cur;
}
printf("%d", ans);
}import java.io.*;
import java.util.*;
public class Main {
private static int L, C;
private static char[] arr;
private static char[] ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
ans = new char[L];
arr = new char[C];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < C ; i++) {
String str = st.nextToken();
arr[i] = str.charAt(0);
}
Arrays.sort(arr);
recur(0, 0);
}
public static void recur(int where, int from) {
// final condition
if (where == L) {
if (check()) {
System.out.println(new String(ans));
}
return;
}
for (int i = from ; i < C ; i++) {
ans[where] = arr[i];
// public static void recur(int where, int from)
// 이 점에 미리 자음이랑 모음 개수를 세어놓을 수 있다.
// 중간에 잘하면 가지치기도 가능
recur(where + 1, i + 1);
}
}
public static boolean check() {
int countMoeum = 0, countJaeum = 0;
boolean[] isMoeum = new boolean[128];
isMoeum['a'] = true;
isMoeum['e'] = true;
isMoeum['i'] = true;
isMoeum['o'] = true;
isMoeum['u'] = true;
for (int i = 0 ; i < L ; i++) {
if (isMoeum[ans[i]]) countMoeum++;
else countJaeum++;
}
return countMoeum >= 1 && countJaeum >= 2;
}
}1103 #include <cstdio>
int n, m, ans, dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1}, limit;
int max_count[50][50]; // 시작부터 가장 많이 점프 한 횟수
char board[50][51];
void dfs(int y, int x, int cnt) {
if (ans < cnt) ans = cnt;
if (ans > limit) return;
// 예외 처리
if (y < 0 || n <= y || x < 0 || m <= x || board[y][x] == -1) return;
if (cnt <= max_count[y][x]) return;
max_count[y][x] = cnt;
int mul = board[y][x];
for (int i = 0 ; i < 4 ; i++) {
dfs(y + dy[i] * mul, x + dx[i] * mul, cnt + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
limit = n * m;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < m ; j++) {
// 처음 시작 점프 횟수가 0일 예정이라서 0보다 작은 -1로 초기화를 했는데,
// 다른 방식으로도 구현이 가능합니다.
max_count[i][j] = -1;
}
}
for (int i = 0 ; i < n ; i++) {
scanf("%s", board[i]);
for (int j = 0 ; j < m ; j++) {
if (board[i][j] == 'H') board[i][j] = -1;
else board[i][j] -= '0';
}
}
dfs(0, 0, 0);
if (ans > limit) ans = -1;
printf("%d", ans);
}
2580 #include <cstdio>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii> empty_space;
int sudoku[9][9];
// pos에 있는 empty_space를 어떤숫자로 채울지 판단
void recur(int pos) {
// final condition
if (pos == empty_space.size()) {
// 출력하고
// 끝냄
return;
}
for (int i = 0 ; i <= 9 ; i++) {
// 앞으로 할 일은 empty_space를 0 ~ 9 로 채워보는 건데
// 언제채울 수 있냐면
// 1. empty_space가 있는 작은 사각형에 숫자가 중복이 안될때! ==> 그 작은 사각형을 어떻게 판단할지
// 2. empty_space가 있는 세로줄에 숫자가 중복이 안될때 ==> 세로줄을 어떻게 판단할지??
// 3. empty_spcae가 있는 가로줄에 숫자가 중복이 안될때 ==> 가로줄을 어떻게 판단할지???
// 1, 2, 3이 만족이 되면 일단 "그 숫자"로 채워보고
recur(pos + 1);
// 만약에 정답을 찾았으면 끝내는 방향으로 가고
// 못찾았으면 다른 숫자로 채워보고...
}
}
int main() {
// 입력을 받은 다음에
// 빈 공간들("0")을 모은다 (y, x) --> empty_space
// 모든 empty_space를 어떤 값으로 다 채웠다고 판단하면 그 상태가 정답이므로 출력을 한다.
}
1339 #include <cstdio>
#include <vector>
using namespace std;
int n, alpha_cnt; // alpha_cnt : 서로다른 알파벳의 갯수
int ans;
char word[10][10];
bool check[128];
bool used[10];
int mapping[10];
vector<char> alpha;
// mapping 0 1 2 3 4 5 ==> 순열로 나열할 것임
// value 9 7 1 2 5 6
// alpha Z A X Y D E
// 알파벳에 매핑된 숫자를 반환
int toNum(char c) {
for (int i = 0 ; i < alpha_cnt ; i++) {
if (alpha[i] == c) {
return mapping[i];
}
}
return 0;
}
// k번째 문자열을 숫자로 반환
int getNum(int k) {
int res = 0;
//"ABCDE"
//"98765"
//9 98 987 9876 98765
for (int i = 0 ; word[k][i] !=0 ; i++) {
int num = toNum(word[k][i]);
res *= 10, res += num;
}
return res;
}
int calc() {
int sum = 0;
for (int i = 0 ; i < n ; i++) {
sum += getNum(i);
}
return sum;
}
// 매핑된 숫자로 뭔가 계산
// 알파벳에 매핑할 숫자들 경우를 일이 구해보는 것
void brute_force(int who) {
// final condition
if (who == alpha_cnt) {
int tmp = calc();
if (ans < tmp) {
ans = tmp;
}
// debug
/*
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%c ", alpha[i]);
}
printf("\n");
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%d ", mapping[i]);
}
printf("\n");
printf("\n");
*/
return;
}
for (int i = 0 ; i <= 9 ; i++) {
if (used[i]) continue;
used[i] = true;
mapping[who] = i;
brute_force(who + 1);
mapping[who] = 0; // 꼭 하지는 않아도 됨
used[i] = false;
}
}
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", word[i]);
// 문자열 끝까지 읽는 다는 뜻(마지막 값은 0임 C++에서)
for (int j = 0 ; word[i][j] != 0 ; j++) {
if (!check[word[i][j]]) {
alpha_cnt++;
check[word[i][j]] = true;
alpha.push_back(word[i][j]);
}
}
}
// 작업 - 숫자들을 하나씩 매핑 해보는 경우의 수
brute_force(0);
printf("%d", ans);
}
// 알파벳이 주어지면
// 알파벳별로 숫자를 하나씩 매핑해보는게 일입니다.
// 최대 10개가 주어지는데....경우의수?????
// 이렇게 만든 경우의수에 대해서
// 직접 숫자을 대입해서 합을구하고, 최대값을 찾는다....
// 두번째 ==> 숫자를 그대로이용하는 방법
// ABCD : 1000 * A + 100 * B + 10 * C + D
// GCD : 100 * G + 10 * C + D
// EFABC : 10000 * E + 1000 * F + 100 * A + 10 * B + C
// ----------------------------------------------------
// 1100 * A + 110 * B + 21 * C + 2 * D + 10000 * E + 1000 * F + 100 * G
2003 import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static int[] A;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
// 완전탐색 비슷하게
// 투포인터는??
int s = 0, e = 0, sum = 0;
for (s = 0 ; s < N ; s++) {
for ( ; e < N ; e++) {
sum += A[e];
System.out.printf("[s ~ e] %d %d : %d\n", s, e, sum);
if (sum == M) {
answer++;
break;
}
else if (sum > M) {
break;
}
}
sum -= A[s];
}
System.out.println(answer);
}
}
2805 #include <cstdio>
typedef long long LL;
int n, m;
LL tree[1000000];
LL answer;
bool cutok(LL h) {
LL sum = 0;
for (int i = 0 ; i < n ; i++) {
if (tree[i] > h) {
sum += tree[i] - h;
}
if (sum >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) {
scanf("%lld", &tree[i]);
}
// 높이를 변경해가면서 나무를 잘라보고
// 조건을 만족하는 가장 큰 높이를 찾아본다.....
// 시간 초과가 발생할 것 같음
/*
for (LL h = 0 ; h <= 1000000000 ; h++) {
if (cutok(h)) {
answer = h;
}
else {
break;
}
}
*/
LL bottom = 0, top = 1000000000, mid;
while (bottom <= top) {
mid = (bottom + top) / 2;
if (cutok(mid)) {
if (answer < mid) answer = mid;
bottom = mid + 1;
}
else {
top = mid - 1;
}
}
printf("%lld", answer);
}
1072 import java.io.*;
import java.util.*;
public class Main {
private static long X, Y, Z;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
Z = Y * 100 / X;
if (Z == 100 || Z == 99) {
System.out.println(-1);
return;
}
// 이분 탐색으로 진행
long bottom = 1, top = 1000000000, mid;
long answer = 1000000000;
while (bottom <= top) {
mid = (bottom + top) / 2;
long nextZ = (Y + mid) * 100 / (X + mid);
if (Z < nextZ) {
if (mid < answer) {
answer = mid;
}
top = mid - 1;
}
else {
bottom = mid + 1;
}
}
System.out.println(answer);
//System.out.println("Z : " + Z);
//System.out.println("NEXT Z : " + (Y + answer) * 100 / (X + answer));
/*
// 경기횟수가 정수 범위를 벗어 난다면??????
for (int i = 1 ; ; i++) {
long nextZ = (Y + i) * 100 / (X + i);
double tmp = (double)(Y + i) * 100 / (X + i);
System.out.println(tmp);
if (nextZ != Z) {
System.out.println(i);
break;
}
}
*/
}
}
7453 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}
2842 #include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}
11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
int n, m, ans, dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1}, limit;
int max_count[50][50]; // 시작부터 가장 많이 점프 한 횟수
char board[50][51];
void dfs(int y, int x, int cnt) {
if (ans < cnt) ans = cnt;
if (ans > limit) return;
// 예외 처리
if (y < 0 || n <= y || x < 0 || m <= x || board[y][x] == -1) return;
if (cnt <= max_count[y][x]) return;
max_count[y][x] = cnt;
int mul = board[y][x];
for (int i = 0 ; i < 4 ; i++) {
dfs(y + dy[i] * mul, x + dx[i] * mul, cnt + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
limit = n * m;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < m ; j++) {
// 처음 시작 점프 횟수가 0일 예정이라서 0보다 작은 -1로 초기화를 했는데,
// 다른 방식으로도 구현이 가능합니다.
max_count[i][j] = -1;
}
}
for (int i = 0 ; i < n ; i++) {
scanf("%s", board[i]);
for (int j = 0 ; j < m ; j++) {
if (board[i][j] == 'H') board[i][j] = -1;
else board[i][j] -= '0';
}
}
dfs(0, 0, 0);
if (ans > limit) ans = -1;
printf("%d", ans);
}#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
vector<pii> empty_space;
int sudoku[9][9];
// pos에 있는 empty_space를 어떤숫자로 채울지 판단
void recur(int pos) {
// final condition
if (pos == empty_space.size()) {
// 출력하고
// 끝냄
return;
}
for (int i = 0 ; i <= 9 ; i++) {
// 앞으로 할 일은 empty_space를 0 ~ 9 로 채워보는 건데
// 언제채울 수 있냐면
// 1. empty_space가 있는 작은 사각형에 숫자가 중복이 안될때! ==> 그 작은 사각형을 어떻게 판단할지
// 2. empty_space가 있는 세로줄에 숫자가 중복이 안될때 ==> 세로줄을 어떻게 판단할지??
// 3. empty_spcae가 있는 가로줄에 숫자가 중복이 안될때 ==> 가로줄을 어떻게 판단할지???
// 1, 2, 3이 만족이 되면 일단 "그 숫자"로 채워보고
recur(pos + 1);
// 만약에 정답을 찾았으면 끝내는 방향으로 가고
// 못찾았으면 다른 숫자로 채워보고...
}
}
int main() {
// 입력을 받은 다음에
// 빈 공간들("0")을 모은다 (y, x) --> empty_space
// 모든 empty_space를 어떤 값으로 다 채웠다고 판단하면 그 상태가 정답이므로 출력을 한다.
}1339 #include <cstdio>
#include <vector>
using namespace std;
int n, alpha_cnt; // alpha_cnt : 서로다른 알파벳의 갯수
int ans;
char word[10][10];
bool check[128];
bool used[10];
int mapping[10];
vector<char> alpha;
// mapping 0 1 2 3 4 5 ==> 순열로 나열할 것임
// value 9 7 1 2 5 6
// alpha Z A X Y D E
// 알파벳에 매핑된 숫자를 반환
int toNum(char c) {
for (int i = 0 ; i < alpha_cnt ; i++) {
if (alpha[i] == c) {
return mapping[i];
}
}
return 0;
}
// k번째 문자열을 숫자로 반환
int getNum(int k) {
int res = 0;
//"ABCDE"
//"98765"
//9 98 987 9876 98765
for (int i = 0 ; word[k][i] !=0 ; i++) {
int num = toNum(word[k][i]);
res *= 10, res += num;
}
return res;
}
int calc() {
int sum = 0;
for (int i = 0 ; i < n ; i++) {
sum += getNum(i);
}
return sum;
}
// 매핑된 숫자로 뭔가 계산
// 알파벳에 매핑할 숫자들 경우를 일이 구해보는 것
void brute_force(int who) {
// final condition
if (who == alpha_cnt) {
int tmp = calc();
if (ans < tmp) {
ans = tmp;
}
// debug
/*
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%c ", alpha[i]);
}
printf("\n");
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%d ", mapping[i]);
}
printf("\n");
printf("\n");
*/
return;
}
for (int i = 0 ; i <= 9 ; i++) {
if (used[i]) continue;
used[i] = true;
mapping[who] = i;
brute_force(who + 1);
mapping[who] = 0; // 꼭 하지는 않아도 됨
used[i] = false;
}
}
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", word[i]);
// 문자열 끝까지 읽는 다는 뜻(마지막 값은 0임 C++에서)
for (int j = 0 ; word[i][j] != 0 ; j++) {
if (!check[word[i][j]]) {
alpha_cnt++;
check[word[i][j]] = true;
alpha.push_back(word[i][j]);
}
}
}
// 작업 - 숫자들을 하나씩 매핑 해보는 경우의 수
brute_force(0);
printf("%d", ans);
}
// 알파벳이 주어지면
// 알파벳별로 숫자를 하나씩 매핑해보는게 일입니다.
// 최대 10개가 주어지는데....경우의수?????
// 이렇게 만든 경우의수에 대해서
// 직접 숫자을 대입해서 합을구하고, 최대값을 찾는다....
// 두번째 ==> 숫자를 그대로이용하는 방법
// ABCD : 1000 * A + 100 * B + 10 * C + D
// GCD : 100 * G + 10 * C + D
// EFABC : 10000 * E + 1000 * F + 100 * A + 10 * B + C
// ----------------------------------------------------
// 1100 * A + 110 * B + 21 * C + 2 * D + 10000 * E + 1000 * F + 100 * G
2003 import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static int[] A;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
// 완전탐색 비슷하게
// 투포인터는??
int s = 0, e = 0, sum = 0;
for (s = 0 ; s < N ; s++) {
for ( ; e < N ; e++) {
sum += A[e];
System.out.printf("[s ~ e] %d %d : %d\n", s, e, sum);
if (sum == M) {
answer++;
break;
}
else if (sum > M) {
break;
}
}
sum -= A[s];
}
System.out.println(answer);
}
}
2805 #include <cstdio>
typedef long long LL;
int n, m;
LL tree[1000000];
LL answer;
bool cutok(LL h) {
LL sum = 0;
for (int i = 0 ; i < n ; i++) {
if (tree[i] > h) {
sum += tree[i] - h;
}
if (sum >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) {
scanf("%lld", &tree[i]);
}
// 높이를 변경해가면서 나무를 잘라보고
// 조건을 만족하는 가장 큰 높이를 찾아본다.....
// 시간 초과가 발생할 것 같음
/*
for (LL h = 0 ; h <= 1000000000 ; h++) {
if (cutok(h)) {
answer = h;
}
else {
break;
}
}
*/
LL bottom = 0, top = 1000000000, mid;
while (bottom <= top) {
mid = (bottom + top) / 2;
if (cutok(mid)) {
if (answer < mid) answer = mid;
bottom = mid + 1;
}
else {
top = mid - 1;
}
}
printf("%lld", answer);
}
1072 import java.io.*;
import java.util.*;
public class Main {
private static long X, Y, Z;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
Z = Y * 100 / X;
if (Z == 100 || Z == 99) {
System.out.println(-1);
return;
}
// 이분 탐색으로 진행
long bottom = 1, top = 1000000000, mid;
long answer = 1000000000;
while (bottom <= top) {
mid = (bottom + top) / 2;
long nextZ = (Y + mid) * 100 / (X + mid);
if (Z < nextZ) {
if (mid < answer) {
answer = mid;
}
top = mid - 1;
}
else {
bottom = mid + 1;
}
}
System.out.println(answer);
//System.out.println("Z : " + Z);
//System.out.println("NEXT Z : " + (Y + answer) * 100 / (X + answer));
/*
// 경기횟수가 정수 범위를 벗어 난다면??????
for (int i = 1 ; ; i++) {
long nextZ = (Y + i) * 100 / (X + i);
double tmp = (double)(Y + i) * 100 / (X + i);
System.out.println(tmp);
if (nextZ != Z) {
System.out.println(i);
break;
}
}
*/
}
}
7453 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}
2842 #include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}
11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <vector>
using namespace std;
int n, alpha_cnt; // alpha_cnt : 서로다른 알파벳의 갯수
int ans;
char word[10][10];
bool check[128];
bool used[10];
int mapping[10];
vector<char> alpha;
// mapping 0 1 2 3 4 5 ==> 순열로 나열할 것임
// value 9 7 1 2 5 6
// alpha Z A X Y D E
// 알파벳에 매핑된 숫자를 반환
int toNum(char c) {
for (int i = 0 ; i < alpha_cnt ; i++) {
if (alpha[i] == c) {
return mapping[i];
}
}
return 0;
}
// k번째 문자열을 숫자로 반환
int getNum(int k) {
int res = 0;
//"ABCDE"
//"98765"
//9 98 987 9876 98765
for (int i = 0 ; word[k][i] !=0 ; i++) {
int num = toNum(word[k][i]);
res *= 10, res += num;
}
return res;
}
int calc() {
int sum = 0;
for (int i = 0 ; i < n ; i++) {
sum += getNum(i);
}
return sum;
}
// 매핑된 숫자로 뭔가 계산
// 알파벳에 매핑할 숫자들 경우를 일이 구해보는 것
void brute_force(int who) {
// final condition
if (who == alpha_cnt) {
int tmp = calc();
if (ans < tmp) {
ans = tmp;
}
// debug
/*
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%c ", alpha[i]);
}
printf("\n");
for (int i = 0 ; i < alpha_cnt ; i++) {
printf("%d ", mapping[i]);
}
printf("\n");
printf("\n");
*/
return;
}
for (int i = 0 ; i <= 9 ; i++) {
if (used[i]) continue;
used[i] = true;
mapping[who] = i;
brute_force(who + 1);
mapping[who] = 0; // 꼭 하지는 않아도 됨
used[i] = false;
}
}
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", word[i]);
// 문자열 끝까지 읽는 다는 뜻(마지막 값은 0임 C++에서)
for (int j = 0 ; word[i][j] != 0 ; j++) {
if (!check[word[i][j]]) {
alpha_cnt++;
check[word[i][j]] = true;
alpha.push_back(word[i][j]);
}
}
}
// 작업 - 숫자들을 하나씩 매핑 해보는 경우의 수
brute_force(0);
printf("%d", ans);
}
// 알파벳이 주어지면
// 알파벳별로 숫자를 하나씩 매핑해보는게 일입니다.
// 최대 10개가 주어지는데....경우의수?????
// 이렇게 만든 경우의수에 대해서
// 직접 숫자을 대입해서 합을구하고, 최대값을 찾는다....
// 두번째 ==> 숫자를 그대로이용하는 방법
// ABCD : 1000 * A + 100 * B + 10 * C + D
// GCD : 100 * G + 10 * C + D
// EFABC : 10000 * E + 1000 * F + 100 * A + 10 * B + C
// ----------------------------------------------------
// 1100 * A + 110 * B + 21 * C + 2 * D + 10000 * E + 1000 * F + 100 * Gimport java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static int[] A;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
// 완전탐색 비슷하게
// 투포인터는??
int s = 0, e = 0, sum = 0;
for (s = 0 ; s < N ; s++) {
for ( ; e < N ; e++) {
sum += A[e];
System.out.printf("[s ~ e] %d %d : %d\n", s, e, sum);
if (sum == M) {
answer++;
break;
}
else if (sum > M) {
break;
}
}
sum -= A[s];
}
System.out.println(answer);
}
}2805 #include <cstdio>
typedef long long LL;
int n, m;
LL tree[1000000];
LL answer;
bool cutok(LL h) {
LL sum = 0;
for (int i = 0 ; i < n ; i++) {
if (tree[i] > h) {
sum += tree[i] - h;
}
if (sum >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) {
scanf("%lld", &tree[i]);
}
// 높이를 변경해가면서 나무를 잘라보고
// 조건을 만족하는 가장 큰 높이를 찾아본다.....
// 시간 초과가 발생할 것 같음
/*
for (LL h = 0 ; h <= 1000000000 ; h++) {
if (cutok(h)) {
answer = h;
}
else {
break;
}
}
*/
LL bottom = 0, top = 1000000000, mid;
while (bottom <= top) {
mid = (bottom + top) / 2;
if (cutok(mid)) {
if (answer < mid) answer = mid;
bottom = mid + 1;
}
else {
top = mid - 1;
}
}
printf("%lld", answer);
}
1072 import java.io.*;
import java.util.*;
public class Main {
private static long X, Y, Z;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
Z = Y * 100 / X;
if (Z == 100 || Z == 99) {
System.out.println(-1);
return;
}
// 이분 탐색으로 진행
long bottom = 1, top = 1000000000, mid;
long answer = 1000000000;
while (bottom <= top) {
mid = (bottom + top) / 2;
long nextZ = (Y + mid) * 100 / (X + mid);
if (Z < nextZ) {
if (mid < answer) {
answer = mid;
}
top = mid - 1;
}
else {
bottom = mid + 1;
}
}
System.out.println(answer);
//System.out.println("Z : " + Z);
//System.out.println("NEXT Z : " + (Y + answer) * 100 / (X + answer));
/*
// 경기횟수가 정수 범위를 벗어 난다면??????
for (int i = 1 ; ; i++) {
long nextZ = (Y + i) * 100 / (X + i);
double tmp = (double)(Y + i) * 100 / (X + i);
System.out.println(tmp);
if (nextZ != Z) {
System.out.println(i);
break;
}
}
*/
}
}
7453 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}
2842 #include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}
11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
typedef long long LL;
int n, m;
LL tree[1000000];
LL answer;
bool cutok(LL h) {
LL sum = 0;
for (int i = 0 ; i < n ; i++) {
if (tree[i] > h) {
sum += tree[i] - h;
}
if (sum >= m) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) {
scanf("%lld", &tree[i]);
}
// 높이를 변경해가면서 나무를 잘라보고
// 조건을 만족하는 가장 큰 높이를 찾아본다.....
// 시간 초과가 발생할 것 같음
/*
for (LL h = 0 ; h <= 1000000000 ; h++) {
if (cutok(h)) {
answer = h;
}
else {
break;
}
}
*/
LL bottom = 0, top = 1000000000, mid;
while (bottom <= top) {
mid = (bottom + top) / 2;
if (cutok(mid)) {
if (answer < mid) answer = mid;
bottom = mid + 1;
}
else {
top = mid - 1;
}
}
printf("%lld", answer);
}import java.io.*;
import java.util.*;
public class Main {
private static long X, Y, Z;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
X = Long.parseLong(st.nextToken());
Y = Long.parseLong(st.nextToken());
Z = Y * 100 / X;
if (Z == 100 || Z == 99) {
System.out.println(-1);
return;
}
// 이분 탐색으로 진행
long bottom = 1, top = 1000000000, mid;
long answer = 1000000000;
while (bottom <= top) {
mid = (bottom + top) / 2;
long nextZ = (Y + mid) * 100 / (X + mid);
if (Z < nextZ) {
if (mid < answer) {
answer = mid;
}
top = mid - 1;
}
else {
bottom = mid + 1;
}
}
System.out.println(answer);
//System.out.println("Z : " + Z);
//System.out.println("NEXT Z : " + (Y + answer) * 100 / (X + answer));
/*
// 경기횟수가 정수 범위를 벗어 난다면??????
for (int i = 1 ; ; i++) {
long nextZ = (Y + i) * 100 / (X + i);
double tmp = (double)(Y + i) * 100 / (X + i);
System.out.println(tmp);
if (nextZ != Z) {
System.out.println(i);
break;
}
}
*/
}
}7453 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}
2842 #include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}
11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
vector<int> a, b, c, d;
vector<int> ab, cd;
LL st1() {
// 전략 1. 정렬 없이 바로 map 사용
}
LL st2_1() {
// 전략 2. 정렬 ==>
// 전략 2-1. lower_bound, upper_bound
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
}
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
int target = -ab[p_ab];
if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
res += cnt;
}
else {
while (0 <= p_cd && target < cd[p_cd]) {
p_cd--;
}
cnt = 0;
while (0 <= p_cd && target == cd[p_cd]) {
cnt++;
p_cd--
}
res += cnt;
}
}
return res;
}
/*
LL st2_2() {
LL res = 0, cnt = 0;
// 전략 2. 정렬 ==>
// 전략 2-2. 안쓰고 ==>
sort(ab.begin(), ab.end());
sort(cd.begin(), cd.end());
int p_cd = cd.size() - 1;
for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
res += cnt;
}
else {
cnt = 0;
while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
res += cnt;
}
}
return res;
}
*/
int main() {
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int u, v, w, x;
scanf("%d%d%d%d", &u, &v, &w, &x);
a.push_back(u);
b.push_back(v);
c.push_back(w);
d.push_back(x);
}
// a,b 로 만들수 있는 합의 조합 ==> ab
// c,d로 만들수 있는 합의 조합 ==> cd
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
ab.push_back(a[i] + b[j]);
cd.push_back(c[i] + d[j]);
}
}
//printf("%lld", st_1());
//printf("%lld", st_2_1());
printf("%lld", st2_2());
}#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, h[50][50], dy[] = {-1, 1, 0, 0, -1, -1, 1, 1}, dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int cnt_k, y_post, x_post;
char vil[50][51];
vector<int> hhh;
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
int bfs(int low, int high) {
// to-do
int cnt = 0;
bool vt[50][50] = {false, };
queue<pii> q;
q.push(pii(y_post, x_post));
vt[y_post][x_post] = true;
if (h[y_post][x_post] < low || high < h[y_post][x_post]) return -1;
while (!q.empty() && cnt < cnt_k) {
pii cur = q.front();
q.pop();
for (int i = 0 ; i < 8 ; i++) {
int nxty = cur.first + dy[i], nxtx = cur.second + dx[i];
if (nxty < 0 || n <= nxty || nxtx < 0 || n <= nxtx) continue;
if (vt[nxty][nxtx]) continue;
if (h[nxty][nxtx] < low || high < h[nxty][nxtx]) continue;
if (vil[nxty][nxtx] == 'K') {
cnt++;
}
vt[nxty][nxtx] = true;
q.push(pii(nxty, nxtx));
}
}
return cnt;
}
// low ~ high의 고도사이로 탐색을 했을때, 배달 할 수 있는 집의 개수를 리턴
//int dfs(int low, int high) {
// // to-do
//}
int main() {
freopen("res/B2842.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%s", vil[i]);
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
if (vil[i][j] == 'K') {
cnt_k++;
}
else if (vil[i][j] == 'P') {
y_post = i, x_post = j;
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) {
scanf("%d", &h[i][j]);
hhh.push_back(h[i][j]);
}
}
// 하고 싶은 것
// 낮은 높이, 높은 높이를 임의로 정해서 모든 집에 배달 할 수 있는지를 확인하고 싶다
//if (bfs(low, high) == cnt_k) ==> OK
// low, high 모든 경우를 탐색하면 시간이 오래걸릴텐데......
// 1. 이분 탐색을 이용 ==> hint : 특정 low에 대해서 되는 low + "a" 를 찾아보기
// 2. 투포인터를 이용 ==> hint : 특정 시점에서 low-high가 만족을 했을때 다음 스텝은?
sort(hhh.begin(), hhh.end());
int answer = hhh.back() - hhh[0];
for (int low = 0, high = 0 ; low < hhh.size() && high < hhh.size() && low <= high ; ) {
if (bfs(hhh[low], hhh[high]) == cnt_k) {
int tmp = hhh[high] - hhh[low];
if (tmp < answer) {
answer = tmp;
}
low++;
}
else {
high++;
}
}
printf("%d", answer);
}11003 #include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}
5639 import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}
1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <deque>
using namespace std;
int n, l, a;
deque< pair<int, int> > q;
int main() {
scanf("%d%d", &n, &l);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a);
while (!q.empty()) {
pair<int, int> t = q.back();
if (t.second >= a) q.pop_back();
else break;
}
q.push_back(make_pair(i, a));
pair<int, int> t = q.front();
if (t.first == i - l) q.pop_front(), t = q.front();
printf("%d ", t.second);
}
}import java.io.*;
import java.util.*;
public class Main {
// file???
// cpp cin.eof() == true
// while (cin >> preorder[i++]);
// scanf("%d", &a) == -1 끝
// freopen("res/test.in", "r", stdin);
private static int[] a = new int[10000];
private static int sz;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/test.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str = br.readLine()) != null) {
a[sz] = Integer.parseInt(str.trim());
sz++;
}
recur(0, sz - 1);
}
private static void recur(int s, int e) {
// a[s] == 전위 순회에서는 root
if (s == e) {
System.out.println(a[s]);
return;
}
else if (s > e) {
return;
}
else {
int where = s + 1;
while (where <= e) {
if (a[where] > a[s]) break;
else where++;
}
// left
recur(s + 1, where - 1);
// right
recur(where, e);
System.out.println(a[s]);
}
}
}1655 #include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}
3020 #include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}
1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;
int n;
int main() {
freopen("res/B1655.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int a;
scanf("%d", &a);
// processing
if (min_pq.size() == max_pq.size()) {
// to max_pq
max_pq.push(a);
}
else {
// to min_pq
min_pq.push(a);
}
if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
int min_value = min_pq.top();
min_pq.pop();
int max_value = max_pq.top();
max_pq.pop();
max_pq.push(min_value);
min_pq.push(max_value);
}
//min_pq.top() < max_pq.top() ==> 바꾼다..
// print
printf("%d\n", max_pq.top());
}
}#include <cstdio>
int n, h, answer, count;
int seok[200000], jong[200000];
// x구간으로 날아갈때 k번째 석순과 만나는지
bool check_seok(int k, int x) {
if (x <= seok[k]) return true;
return false;
}
// x구간으로 날아갈때 k번째 종유석과 만나는지
bool check_jong(int k, int x) {
if (h - jong[k] + 1 <= x) return true;
return false;
}
int fly(int x) {
int res = 0;
for (int i = 0 ; i < n ; i += 2) {
// 석순과 만나는지
if (check_seok(i, x)) res++;
// 종유석과 만나는지
if (check_jong(i, x)) res++;
}
return res;
}
int main() {
scanf("%d %d", &n, &h);
for (int i = 0 ; i < n ; i += 2) {
scanf("%d", &seok[i]);
scanf("%d", &jong[i]);
}
answer = -1;
for (int i = 1 ; i <= h ; i++) {
int crash = fly(i);
if (answer == -1 || crash < answer) {
answer = crash;
count = 1;
}
else if (crash == answer) {
count++;
}
}
printf("%d %d", answer, count);
}1202 import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}
2517 #include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}
11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.io.*;
import java.util.*;
// "보석도둑"
public class Main {
private static int N, K;
private static long answer;
//private static int[][] jewe;
private static Info[] boseok;
private static int[] gabang;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
boseok = new Info[N];
gabang = new int[K];
for (int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
boseok[i] = new Info(m, v);
}
for (int i = 0 ; i < K ; i++) {
st = new StringTokenizer(br.readLine());
gabang[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(boseok, new Comparator<Info>() {
@Override
public int compare(Info arg0, Info arg1) {
// int라서 이렇게 사용
// long이면 직접 비교 수행하셔야합니다!
return arg0.m - arg1.m;
}
});
Arrays.sort(gabang);
// 가방이 작은것 부터 무엇을 넣어야할지 판단해본다.
int posBoseok = 0;
//List<Integer> candBoseok = new ArrayList<Integer>; 너무 힘듬...매번정렬해야할지도...
PriorityQueue<Integer> pq; // 보석의 value를 넣을 것이다
pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
}
});
for (int i = 0 ; i < K ; i++) {
int curGabang = gabang[i];
while (posBoseok < N && boseok[posBoseok].m <= curGabang) {
pq.add(boseok[posBoseok].v);
posBoseok++;
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
// // 보석 후보중에서 가장 가치가 높은것을 찾아서 answer +=
// //for (int i = 0 ; i < candBoseok.size() ; i++) {
// // find max
// }
// // ans++
// // max 사용했다고 처리도 해야함..
}
System.out.println(answer);
}
static class Info {
int m, v;
Info (int m, int v) {
this.m = m;
this.v = v;
}
}
}#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, num;
pii player[500000];
int tr[1<<20];
int seg_sum(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) {
//return node; 틀림
return tr[node];
}
else {
return seg_sum(node * 2, s, (s + e) / 2, l, r) + seg_sum(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
}
void update(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
tr[node] = v;
/*
tr[node] += v;
tr[node] -= v;
tr[node] ^= v;
tr[node] *= v;
tr[node] &= v;
*/
}
else {
update(node * 2, s, (s + e) / 2, idx, v);
update(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
tr[node] = tr[node * 2] + tr[node * 2 + 1];
}
}
bool comp(pii p1, pii p2) {
return p1.second < p2.second;
}
int main() {
freopen("res/B2517.in", "r", stdin);
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
int power;
scanf("%d", &power);
player[i].first = i;
player[i].second = power;
}
// sort power --> relabeling
sort(player, player + n, comp);
for (int i = 0 ; i < n ; i++) {
player[i].second = ++num; // i + 1
}
// sort original order
sort(player, player + n);
for (int i = 0 ; i < n ; i++) {
int curpower = player[i].second;
int cnt = 0;
if (curpower > 1) {
cnt = seg_sum(1, 1, num, 1, curpower - 1);
}
update(1, 1, num, curpower, 1);
printf("%d\n", i + 1 - cnt);
}
}11653 #include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}
14476 import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
#include <vector>
using namespace std;
bool che[3200];
vector<int> prime;
int n;
int main() {
for (int i = 2 ; i < 3200 ; i++) {
if (che[i]) continue;
for (int j = i + i ; j < 3200 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i < 3200 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
if (n == 1) {
return 0;
}
for (int i = 0 ; i < prime.size() ; i++) {
while (n % prime[i] == 0) {
printf("%d\n", prime[i]);
n /= prime[i];
}
}
if (n > 1) {
printf("%d\n", n);
}
}import java.io.*;
import java.util.*;
public class Main {
private static int N;
private static int[] A;
private static int[] leftGcd, rightGcd;
private static int answer = -1, who;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N + 2];
leftGcd = new int[N + 2];
rightGcd = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 1 ; i <= N ; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1 ; i <= N ; i++) {
leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
}
for (int i = N ; i >= 1 ; i--) {
rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
}
for (int i = 1 ; i <= N ; i++) {
int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
if (A[i] % curGcd == 0) continue;
if (answer < curGcd) {
answer = curGcd;
who = A[i];
}
}
if (answer == -1) {
System.out.println(answer);
}
else {
System.out.println(answer + " " + who);
}
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}10610 #include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}
2904 #include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}
11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
char s[100001];
int sum, count[128];
int main() {
scanf("%s", s);
for (int i = 0 ; s[i] ; i++) {
sum += s[i] - '0';
count[s[i]]++;
}
if (sum % 3 != 0 || count['0'] == 0) {
printf("-1");
return 0;
}
for (int i = '9' ; i >= '0' ; i--) {
for (int j = 0 ; j < count[i] ; j++) {
printf("%c", i);
}
}
}#include <cstdio>
#include <vector>
using namespace std;
bool che[1000001];
int n, a[100];
vector<int> prime;
int count[100][80000]; // 대략 100만 이하 소수가 7xxxx개 있는데.....
int totalCount[80000]; // 전체 숫자에서 소수가 나타난 횟수
int gcdCount[80000]; // gcd가 될 것 같은 횟수
int answer1, answer2; // 가장 큰 점수, 최소 횟수
int main() {
for (int i = 2 ; i <= 1000000 ; i++) {
if (che[i]) continue;
// i is prime
for (int j = i + i ; j <= 1000000 ; j += i) {
che[j] = true;
}
}
for (int i = 2 ; i <= 1000000 ; i++) {
if (!che[i]) {
prime.push_back(i);
}
}
scanf("%d", &n);
for (int i = 0 ; i < n ; i++) {
scanf("%d", &a[i]);
}
// 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해
for (int i = 0 ; i < n ; i++) {
int num = a[i];
for (int j = 0 ; j < prime.size() ; j++) {
while (num % prime[j] == 0) {
count[i][j]++;
totalCount[j]++;
num /= prime[j];
}
}
}
for (int i = 0 ; i < prime.size() ; i++) {
gcdCount[i] = totalCount[i] / n;
}
answer1 = 1;
for (int i = 0 ; i < prime.size() ; i++) {
for (int j = 0 ; j < gcdCount[i] ; j++) {
answer1 *= prime[i];
}
// 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다
for (int j = 0 ; j < n ; j++) {
if (count[j][i] < gcdCount[i]) {
answer2 += gcdCount[i] - count[j][i];
}
}
}
printf("%d %d", answer1, answer2);
}11051 #include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}
1256 import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}
15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <cstdio>
int cache[1001][1001];
int nCr(int n, int r) {
if (r == 0) {
return 1;
}
if (n < r) {
return 0;
}
if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;
if (cache[n][r] != -1) {
return cache[n][r];
}
int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
cache[n][r] = tmp;
return cache[n][r];
}
int main() {
for (int i = 0 ; i <= 1000 ; i++) {
for (int j = 0 ; j <= 1000 ; j++) {
cache[i][j] = -1;
}
}
int n, k;
scanf("%d%d", &n, &k);
printf("%d", nCr(n, k));
}import java.io.*;
import java.util.*;
public class Main {
private static int N, M, K;
private static int[][] cache;
private static char[] answer;
private static final int INF = 1000000010;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cache = new int[101][101];
for (int i = 0 ; i <= 100 ; i++) {
for (int j = 0 ; j <= 100 ; j++) {
cache[i][j] = -1;
}
}
answer = new char[N + M];
if (getAZ(N, M) < K) {
System.out.println(-1);
return;
}
// to-do
// 가장 앞에 있는 문자열부터 채워 나간다
int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자
for (int i = 0 ; i < N + M ; i++) {
// i 번째 문자열이 a라면.....
if (countA > 0) {
int tmp = getAZ(countA - 1, countZ);
if (tmp < K) {
answer[i] = 'z';
K -= tmp;
countZ--;
}
else {
answer[i] = 'a';
countA--;
}
}
else {
answer[i] = 'z';
}
}
System.out.println(new String(answer));
}
public static int getAZ(int a, int z) {
if (a == 0 || z == 0) {
return 1;
}
if (cache[a][z] != -1) {
return cache[a][z];
}
cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
if (cache[a][z] >= INF) {
cache[a][z] = INF;
}
return cache[a][z];
}
}15663 // 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}
Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
// 미완성
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, a[8], answer[8];
bool used[8];
void recur(int k) {
if (k == m) {
for (int i = 0 ; i < m ; i++) {
printf("%d ", answer[i]);
}
printf("\n");
return;
}
for (int i = 0 ; i < n ; i++) {
if (used[i]) continue;
used[i] = true;
// hint...
answer[k] = a[i];
recur(k + 1);
used[i] = false;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0 ; i < n ; i++) scanf("%d", &a[i]);
sort(a, a + n);
recur(0);
}Reference
この問題について([アルゴリズム]sds特別テーマ指導コード1), 我々は、より多くの情報をここで見つけました https://velog.io/@shininghyunho/알고리즘-sds-특강-가이드-코드-1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol